Friday, May 08, 2009

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 
  • 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.


  1. > I no longer have time for a
    > restroom break when I LaTeX a
    > paper.

    Did it really take that long to compile latex?

  2. 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.

  3. 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. A student about to finish her Ph.D.3:36 AM, May 11, 2009

    I am not yet born, but I have been conceived.