Loading ...
Sorry, an error occurred while loading the content.
 

[Computational Complexity] Doctor for Two Decades

Expand Messages
  • Lance
    I measure academic age by years since Ph.D. and by that measure I just turned twenty. I passed my Ph.D. defense on May 5, 1989 (though technically I didn t
    Message 1 of 1 , May 8, 2009
      I measure academic age by years since Ph.D. and by that measure I just turned twenty. I passed my Ph.D. defense on May 5, 1989 (though technically I didn't graduate until June).

      20 years. Wow. 20 years before my Ph.D. we didn't have a P vs. NP problem. Does the PCP theorem seem as ancient to today's grad students as Cook's theorem was to me?

      In those 20 years we had incredible advances in 
      • Complexity of approximations which includes developments of interactive proofs, probabilistically checkable proofs, the parallel repetition theorem, semi-definite programs and unique games.
      • Great advances in coding theory in particular list-decoding codes.
      • Tight connections between circuit hardness and derandomization. And we don't need random coins anymore for primality. 
      • Explicit constructions of extractors, expanders and various other combinatorial objects with SL=L coming out of this theory.
      • Quantum computing.
      • Proof Complexity.
      • Cryptography. Almost anything you can imagine you can implement cryptographically, at least in theory.
      • The applications of computation theory to economic theory and vice versa.
      • Amazing connections between all of the above.
      And I got to watch it all in real time.

      I've seen the Internet go from E-mail to Twitter. I've seen fax machines and CDs go from amazing technologies to has beens. And computers got much faster and smaller. I no longer have time for a restroom break when I LaTeX a paper.

      Technology that hasn't changed much: Transportation. I still get from point A to point B the same way I did twenty years ago though now without being fed. 

      What will the next twenty years bring? Many great theorems. Definitely. Multi-core computers with millions of cores. Probably. Large-scale quantum computers. Doubtful. A proof that P≠NP. Don't count on it.



      --
      Posted By Lance to Computational Complexity at 5/08/2009 07:33:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.