Monday, July 21, 2008

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


  1. Cynthia Dwork -- who I hope won't mind letting me paraphrase her wisdom -- told me once that many successful researchers re-invent themselves by switching areas every decade or so. It's a way both to revitalize one's own interest and to do new groundbreaking work. Certainly Cynthia herself has re-invented herself this last decade, becoming a leader in the fields of privacy and spam-fighting. Many greats -- Valiant, Karp, Adleman, Nisan, I could go on -- have experienced such re-inventions (on various scales). Rather than be depressed about our personal loss when such a switch happens, I think we should hold it up as a model, and laud those courageous enough to seek new challenges, expanding both their scope and the scope of computer science as a field.

  2. Analytic ability goes with age but open-ended creativity can sometimes be enhanced. And so it may make sense to make a career change as one gets older.

  3. Nisan may never had directly worked on quantum computing...

    He has.

  4. Fix for previous link:

  5. Richard Hamming talking about the importance of changing fields:


    The whole thing is at

  6. Noam did remain a theoretical computer scientist, so he walked away from a particular subfield (complexity) to become a founding member of a new subfield (algorithmic game theory), arguably at least as important a contribution to the overall field of TCS. At least he didn't disappear to Wall Street. :-)