[Computational Complexity] The One Who Walked Away
- I caught a rare sighting of Noam Nisan at the GAMES congress. Many of you young complexity theorists may not have ever met Noam or even cite many of his papers anymore. But his research lies at the heart of most of today's complexity research.
Using hard functions for psuedorandom generators started with Nisan who also had breakthroughs in space-bounded generators. Using Forier transforations in complexity got its start with Linial-Mansour-Nisan. Nisan did fundamental work on Communication Complexity and co-wrote the Book on the topic. Nisan may never had directly worked on quantum computing but the polynomial method for proving quantum lower bounds basically follows from Nisan-Szegedy. Not to mention Nisan was the first to show the surprising power of PCPs that led directly to IP = PSPACE and the PCP/Approximation lower bound revolution.
But around 1998 Noam walked away from computational complexity. Just ten years after Ph.D., he felt he had reached his limits in complexity and could no longer produce strong results (despite the fact that he continued to produce papers others could only dream about). Noam shifted gears focusing on economics. Sure he has had his successes there mostly in auction theory. Still what a loss to complexity to lose him over the past decade. If you ever want to return to your roots Noam, we'd be more than happy to have you back.
Posted By Lance to Computational Complexity at 7/21/2008 07:01:00 AM