I've known Noam since we were fellow grad students in Berkeley in 1985 and we have become good friends and colleagues. Noam Nisan started his career in computational complexity and Luca posts about several of his seminal works in derandomization, interactive proofs, communication and circuit complexity. I'll focus this post on Nisan's 1992 paper with Mario Szegedy, On the degree of boolean functions as real polynomials.
Let f be a Boolean function on n variables and p a n-variate polynomial over the reals and suppose for every x in {0,1}n, |f(x)-p(x)| ≤ 1/3. Nisan and Szegedy show that the decision tree complexity of f is bounded by a polynomial in the degree of f. The decision tree complexity of a function is the number of bits one has to query to determine whether f is 0 or 1.
The theorem didn't have an immediate application but soon afterwards I told Noam we found a result that followed from his paper. His ears perked up until I told him the actual result (if P = PSPACE then P = AWPP relative to a Cohen generic oracle).
Later on Nisan-Szegedy would have direct applications to quantum computing, showing that quantum, random and deterministic decision tree complexity for total functions are polynomially related. Just last STOC we saw two papers giving tighter bounds on these relationships.
In 1997 Noam Nisan walked away from complexity and soon thereafter became one of the founding players in algorithmic game theory, co-organizing the 2001 DIMACS workshop that would kickstart this field. He won the 2012 Gödel Prize for his early work on algorithmic mechanism design with Amir Ronen.
Nisan and Szegedy begat one of my most frustrating open questions on the relationship between rational functions and decision tree complexity. I have an application for it but I don't think you really want to know.
Lance, the Knuth Prize is certainly one of most prestigious awards in TCS, but I wonder what makes it "the highest honor in theoretical computer science" in your opinion.
ReplyDeleteWe have a number of high-profile awards in TCS. Some are (early) career awards; others are for highly influential papers. Some are specific to some areas; others cover the whole of TCS in the broadest sense. It is hard to compare those awards and I wonder whether we should do so at all.
Let's celebrate the awards received by members of the TCS community by highlighting the impact of the work behind them, just like Luca Trevisan and you have done so well in your respective blog posts.