Profiles
- An
Influential Theoretician. Paul Hyman, Communications
of the ACM, 2012.
Education
- SB in Math with Computer Science, MIT, 1990. (Also attended IIT Kanpur in India 1986-88 before transfering.)
- PhD in Computer Science, UC Berkeley, 1994. Dissertation topic: Probabilistic checking of proofs and the hardness of approximation problems. Advisor: Umesh Vazirani.
Professional Appointments
- Assistant Professor, Princeton University, Sept 1994.
- Associate Professor, Princeton University, Feb 1999.
- Professor, Princeton University, Sept 2003.
- Charles C. Fitzmorris Professor, Sept 2011.
- Distinguished Visiting Professor,
Institute for Advanced Study, 2017-20.
- Visiting appointments
at UC Berkeley, Microsoft Research,Weizmann Institute,
Kyoto University (2013, 2022), EPFL (2013), ETH (2022), DeepMind London (2023) - Founding Director,
Princeton Language and Intelligence, 2023.
Awards and Honors
- 30-year Test of Time Award for FOCS 1993 (2023)
- Bell Labs Innovation Prize 2020 (Runner-up team)
- Plenary Speaker, International Congress of Mathematicians, 2018
- Inducted as
Member, National Academy of Science, 2018
- Elected to
American Academy of Arts and Sciences, 2015.
- Simons
Investigator, 2012-continuing
- AMS-MOS D.R. Fulkerson Prize, 2012.
- ACM-Infosys Foundation Award in the Computing Sciences , 2011.
- Best paper, IEEE Foundations of Computer Science, 2010.
- EATCS-SIGACT Goedel Prize, 2010.
- Elected ACM Fellow, 2009.
- Engineering Council Teaching Award for Fall 2008, Princeton University.
- Graduate Mentoring Award, Princeton University, 2005.
- Best Paper, ACM Symposium on Theory of Computing, 2004.
- Semiplenary speaker, International Symposium on Math Programming, 2003.
- Distinguished Alumnus Award, UC Berkeley Computer Science, 2003.
- Invited
speaker in Math Aspects of Computer Science session,
International Congress of Mathematicians (ICM), 2002.
- EATCS-SIGACT Goedel Prize, 2001.
- Plenary speaker, ACM Symposium on Theory of Computing, 1998.
- David and Lucile Packard Foundation Fellowship, 1997-2002.
- Alfred P. Sloan Fellowship, 1996.
- NSF CAREER Award, 1995.
- ACM
Doctoral Dissertation Award, (cowinner)1995.
- IBM Graduate
Fellowship, 1993.
- Ranked first
in India, IIT Joint Entrance Exam, 1986.
Professional Service
- Founding director and lead PI, Center for Computational Intractability, Princeton. 2008.
- SIGACT Committee for Advancement of Theoretical CS. Member 2005-07, Chair 2007-2010.
- Served on editorial boards for Computational Complexity, Theory of Computing, SIAM J. Disc. Math, Journal of Combinatorial Optimization, Information and Computation.
- Program chair for IEEE FOCS 2006 and APPROX 2003. PC member for ACM STOC 1996, 2003, 2016, IEEE FOCS in 2000, 2009, and Computational Complexity 2010.
- Coauthor (with
B. Barak) of Computational
Complexity: A Modern Approach. 2009
PhD Students
George
Karakostas, Subhash
Khot, Iannis
Tourlakis, Elad Hazan,
Satyen Kale, David
Steurer, Eden
Chlamtac, Rong Ge, Rajsekar
Manokaran, Chris Beck,
Sushant
Sachdeva Tengyu Ma,
Andrej
Risteski, Yuanzhi LiHolden Lee, Wei Hu, Yi Zhang, Zhiyuan Li, Orestis Plevrakis, Yuping Luo, Nikunj Saunshi.
Postdoc advisees (many over the years)
Personal Info
US Citizen. Born January 1968 in Jodhpur, India.Links to news articles that mention my work
- New short cut found for long math proofs, by Gina Kolata. New York Times, April 7 1992.
- Proof at a Roll of the Dice, by Bernard Chazelle. Nature, 21/28 Dec, 2006.
- Limits of computability, by David Lindley. Communications of ACM, Nov 2008.
- Great unknowns, by Carolyn Johnson. Boston Globe, Feb 9 2009.
- Princeton
study questions derivative computational model. Robert
Butche. News Magazine, May 5 2010.
- Sales and Chips, by Joe Malkevitch. American Math Society, 2012.
- Approximately
hard: the Unique Games Conjecture.