Computational Complexity

Friday, May 08, 2009

 
Doctor for Two Decades

Posted by 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 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.

7:33 AM # 5 comments

1.  Anonymous says:  
   
   > I no longer have time for a
   > restroom break when I LaTeX a
   > paper.
   
   Did it really take that long to compile latex?
   

   12:47 PM, May 08, 2009

2.  Anonymous says:  
   
   Did it really take that long to compile latex?I don't know about a paper, but I was doing TeX in 1988 or so and you had time for a full one hour lunch break when compiling your thesis on a PC.
   

   12:57 PM, May 08, 2009

3.  Janos says:  
   
   Lance, just to make you feel young---I got my PhD (again date of defense, not conferral) 35 years ago.
   
   We definitely did have P vs. NP by then (and much earlier if you accept the Godel letter or Edmonds' references). We also had Kolmogorov Complexity, the Speedup Theorem and hierarchy theorems.
   
   As for LaTex compilation time -- yes, it definitely could take forever. And LaTex itself was a huge improvement over plain Tex, which was MUCH better than nroff/troff that came on the first Unix systems, and those were a HUGE improvement over having to TYPE your paper....
   
   ...although you did not actually type it: departments had technical typists who would do it. Not too many opportunities to revise or rewrite stuff, and turnaround times measured in days (or more if you were a mere student). My thesis was actually typed by a secretary I paid, and it took weeks....
   

   4:55 PM, May 08, 2009

4.  Luca says:  
   
   Happy anniversary!
   

   7:46 PM, May 08, 2009

5.  A student about to finish her Ph.D. says:  
   
   I am not yet born, but I have been conceived.
   

   3:36 AM, May 11, 2009

Comment Feeds: This Post All