ACM Fellows
USA - 2008
citation
For contributions to algorithms and complexity theory.
ACM Doctoral Dissertation Award
USA - 1993
citation
For his dissertation "Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems."