Khot, Subhash

Subhash Khot

Professor of Computer Science

Subhash Khot obtained his bachelor's degree in computer science in 1999 from the Indian Institute of Technology, Bombay, and his doctorate in computer science in 2003 from Princeton University. After a year at the Institute for Advanced Study, he joined Georgia Tech as an assistant professor in 2004, and moved to the Courant Institute, NYU, in 2007, first as associate professor, and then, effective 2012, as professor of computer science.

Professor Khot's specialty is computational complexity. This studies the inherent difficulty of computational tasks, attempting to determine which computational problems can be solved with little computation, which problems can be solved only with large amounts of computation, and which cannot be solved at all. The area has been intensely studied by theoretical computer scientists and mathematicians for fifty years, and is now a highly sophisticated, deep, and complex mathematical theory. A central question in this field is the so-called ``P=NP" question, which, despite intense study, still remains an open question.

Khot's most celebrated work, and the one that led to his recent Nevanlinna Prize, is on the ``Unique Games conjecture''. He introduced this in 2002 and since then has led the community's steady efforts to understand its deep and surprising implications, to find connections to other areas, and to prove (or disprove!) it. Today, this question is the most studied conjecture in theoretical computer science.

The conjecture addresses the main question in computational complexity: how hard are problems to solve or approximate? For over three decades, the main approach to this question was through NP-hardness: namely, we provide strong evidence for the hardness of a problem by showing that it is as hard as any other problem in the class NP. Assuming that NP contains hard problems, as most experts strongly believe, we deduce that our problem is hard. This paradigm has been extremely fruitful and has led to a complete understanding of some important combinatorial optimization problems. Yet, a large number of problems did not succumb to this approach, and their hardness remained a mystery for many years.

Khot's Unique Games conjecture (UGC), introduced in his ingenious 2002 paper, turned out to be the missing key. His conjecture says that the so-called Unique Games problem, a mild variant of the standard NP-complete constraint satisfaction problem, is hard. So in order to show that a problem is hard based on UGC, one needs to show that it is as hard as the Unique Games problem. Using the UGC, one can show that many natural optimization questions are hard. Moreover, one can often nail down precisely the best approximation factor achievable. In a series of remarkable papers by Khot and others, it was then realized that for a large family of problems, the UGC gives the precise approximability factors.

Subhash Khot's research has received extraordinary levels of recognition and honor.  In 2014 he won the Rolf Nevanlinna Prize, the highest scientific award in theoretical computer science, awarded once every 4 years at the International Congress of Mathematicians, for outstanding contributions in Mathematical Aspects of Information Sciences. In 2010 he was awarded the NSF Alan T. Waterman award, given annually to a single scientist in the U.S. aged 35 or younger. He was named a Simons Foundation Investigator in 2015. In 2010 he was an invited speaker at the International Congress of Mathematicians.  He has received an NSF CAREER award, a Sloan Foundation Fellowship, and a Microsoft New Faculty Fellowship.