Monday, December 19, 2005

Favorite Theorems: First Decade Recap

After I chose my ten favorite theorems in the decades 1985-1994 and 1995-2004, I went back to the first decade in complexity. Here is a recap of my ten favorite theorems in computational complexity from 1965-1974. I wrote the first two lists at the end of their respective decades but for this last one we have over thirty years of perspective. For example, at the time one might have included some of the difficult results that related the complexity of different Turing machine models (number of tapes, number of heads, number of dimensions of tapes and others) that seem less important today.

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

Posted by at

11 comments:

  1. ramakrishna u8:03 AM, December 19, 2005

    Very nice list.

    ReplyDelete
  2. Anonymous8:34 AM, December 19, 2005

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

    Amar
    PS: Is voting allowed:)?

    ReplyDelete
  3. GASARCH12:48 PM, December 19, 2005

    Looking over my guest post on SURPRISING theorems,
    and 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

    ReplyDelete
  4. Anonymous12:57 PM, December 19, 2005

    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.

    ReplyDelete
  5. Anonymous2:46 PM, December 19, 2005

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

    Though 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

    ReplyDelete
  6. Anonymous3:24 PM, December 19, 2005

    It seems a bit of a stretch to view the Diffie-Hellman and RSA papers as being papers on complexity; 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).

    ReplyDelete
  7. Anonymous3:52 PM, December 19, 2005

    To digress:

    The 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

    ReplyDelete
  8. Anonymous4:11 PM, December 19, 2005

    On a VERY DIFFERENT topic:
    It'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 :-)

    ReplyDelete
  9. Anonymous4:36 PM, December 19, 2005

    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.

    ReplyDelete
  10. Anonymous5:20 PM, December 19, 2005

    Let 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).

    Of course, it is Lance's favorite list!

    ReplyDelete
  11. Anonymous2:21 AM, December 20, 2005

    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.

    Bryant'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.

    ReplyDelete

Subscribe to: Post Comments (Atom)