[Computational Complexity] Doctor for Two Decades
- 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
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.
- 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.
Posted By Lance to Computational Complexity at 5/08/2009 07:33:00 AM