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
But around 1997 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
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.