1991 Fulkerson Prize in Discrete Mathematics.
Awarded by the Americam Mathematical Society and the Mathematical Programming Society.
Jointly with Martin Dyer and Ravi Kannan for the paper
A random polynomial time algorithm for approximating the volume of convex bodies
Journal of the Association for Computing Machinery 38 (1991) 1-17.

1997 Guggenheim Fellow

2000 IBM Faculty Partnership Award

2006 Professor Pazy Memorial Research Award.
Jointly with Michael Krivelevich.
Awarded by the United States-Israel Binational Science Foundation.

2011 SIAM Fellow

2013 AMS Fellow

2014 Plenary speaker at the International Congress of Mathematicians, Seoul, S. Korea.

2015 Simons Foundation Fellow