- The Seminal Paper (Hartmanis-Stearns)
- Efficient Computation (Cobham-Edmonds)
- NP-Completeness (Cook)
- Combinatorial NP-Complete Problems (Karp)
- The Polynomial-Time Hierarchy (Meyer-Stockmeyer)
- P = NP for Space (Savitch)
- Abstract Complexity (Blum)
- NP-Incomplete Sets (Ladner)
- Logical Characterization of NP (Fagin)
- Defining the Future (Cook-Reckhow)

We have one missing decade, so some more list making next year.

Very nice list.

ReplyDeleteWould really like to see Tarjan's ACKerman paper in the missing list.

ReplyDeleteAmar

PS: Is voting allowed:)?

Looking over my guest post on SURPRISING theorems,

ReplyDeleteand just taking those in 1974-1985 (the missing decade),

and taking out those in algorithms, here are 5 results

that should be in SOMEONES Top 10 of that Decade.

Are they in Lances?

We'll find out at some later time.

ALL are NICE theorems. The only reason they would NOT be in

is if someone found 6 nicer ones, so something has to go.

I did not include UNION-FIND since thats really algorithms,

though it is a nice theorem.

P vs NP cannot be solved by techniques that relatives (Baker, Gill, Solovay 1975).

Public Key Crypto (Diffie Helman, 1976, IEEE Trans Inform Theory, Rivest-Shamir-Adelman, 1978)

Permanent is #P complete. (Valiant 1979)

Bit commit --> SAT in ZK (Brassard,Crepeau FOCS86, Goldreich,Micali,Wigderson CRYPTO86, JACM91)

NSPACE(n) = coNSPACE(n). (1987-Szelepcsenyi-BEATCS, Immerman-1988-IEEECCC, SICOMP).

~ Bill Gasarch

I think one other innovation from that decade was Ordered Binary Decision Diagrams (OBDDs). Though not exactly complexity theory, OBBDs and their algorithms have revolutionized other fields of computer science. The OBDD paper is the most cited paper in computer science, according to Citeseer.

ReplyDeleteYes, I agree. nice is "too simplistic and not too nice" word to describe theorems. Thanks!

ReplyDeleteThough It seems to me that UNION-FIND is not just algorithms. If we are talking just about the hardest problems in NP, then it does not fit in. OTOH, if we are talking about the theory of lower bounds of all problems in NP in general (not just the hardest ones), it does fit in.

Amar

It seems a bit of a stretch to view the Diffie-Hellman and RSA papers as being papers on

ReplyDeletecomplexity; in fact, I would barely call them theory papers (though I do not argue that they had huge impact and are seminal papers, nor that they influenced much later work in theory and complexity).To digress:

ReplyDeleteThe OBDD paper is the most cited paper in computer science, according to Citeseer.

That is true. But Citeseer does not handle well those CS papers that appear in the non-CS literature (as well as the citations from such papers). Based on Google Scholar, there is (an arguably CS) paper with higher citation count:

"Basic local alignment search tool"

� , W Gish, W Miller, EW Myers, DJ Lipman, DJ - J. Mol. Biol, 1990

Cited by 14181

compared to

"Graph-based algorithms for Boolean function manipulation"

RE Bryant� - IEEE Transactions on Computers, 1986

Cited by 3511

On a VERY DIFFERENT topic:

ReplyDeleteIt's worth noting that the number of ECCC reports this year is at a record breaking 158.

Hint to Lance: a post on ECCC's contribution to disseminating complexity research :-)

Re: the last comment, just among the last 30 reports on ECCC, there are solutions to three major open problems, in coding theory, game theory and linear programming respectively. What is most encouraging is that these results appear on ECCC without consideration to artificial boundaries drawn by some people (for purely political reasons) between complexity, algorithms and other fields of theory.

ReplyDeleteLet me throw in one more: Khachiyan's result and the ones following it (Karmarkar-Karp, Papadimitrou) for solving LP problems, and thereby solving a whole set of combinatorial problems. Made one more problem drop into the set of P (in a previously not thought of way).

ReplyDeleteOf course, it is Lance's favorite list!

Closure of space under complement was already on Lance's list for the 1985-1994 decade and computational zero-knowledge proofs also are in the wrong decade for the upcoming list.

ReplyDeleteBryant's OBDD paper was 1986 as well.

Randomized computation in the form of Solovay-Strassen/Rabin-Miller primality testing and Schwartz-Zippel identity testing should not be excluded because they are 'algorithmic'. BPP and RP would be have been relatively boring classes without these algorithms to liven them up.