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.

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.

> I no longer have time for a

ReplyDelete> restroom break when I LaTeX a

> paper.

Did it really take that long to compile latex?

ReplyDeleteDid 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.Lance, just to make you feel young---I got my PhD (again date of defense, not conferral) 35 years ago.

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

Happy anniversary!

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

ReplyDelete