ACM Fellows
United States – 2008
CITATION

For contributions to algorithms and complexity theory.

Doctoral Dissertation Award
United States – 1993
CITATION

For his dissertation "Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems."