Subhash Khot

About Subhash's Work

Subhash Khot is a theoretical computer scientist whose work is providing critical insight into unresolved problems in the field of computational complexity. Since the 1970s, one of the major questions in theory of computing has been whether or not P = NP. That is, can every problem whose solution can be quickly verified by a computer also be quickly solved by a computer? Most computer scientists believe that P does not equal NP—that there are problems, known as NP-hard problems, for which a solution cannot be found efficiently by an algorithm. Thousands of practical problems, from the best way to design a computer chip to optimal airplane schedules, have been shown to be NP-hard.

Over the past two decades, most research in this area has focused on whether, and how well, solutions to these problems can be approximated. To this discussion, Khot contributed the Unique Games Conjecture (UGC), which proposes that for one specific problem about assigning colors to the nodes of a network according to a set of constraints, finding even an approximate solution is NP-hard. While seemingly a simple statement with limited applicability, the UGC has spurred novel and unexpected research. Work by Khot and others has demonstrated that although it is as yet unproven, the conjecture sheds new light on the computational complexity of many, very diverse, optimization tasks. If true, then solutions to a host of problems, many of them seemingly unrelated to the original problem of the UGC, are also too hard to approximate. Even if the UGC ultimately is found to be false, efforts to prove it have led to new theorems in geometry, Fourier analysis, the mathematics of foams, and even the stability of different election systems.

As computers come to drive ever more aspects of our lives, greater understanding of the limitations of computing is increasingly important. Khot’s continued ingenuity and tenacity in exploring the potential of the UGC will drive this important and fruitful area of research for many years to come.

Biography

Subhash Khot received a B.Tech. (1999) from the Indian Institute of Technology, Bombay, and a Ph.D. (2003) from Princeton University. He is currently Silver Professor of Computer Science in the Courant Institute of Mathematical Sciences at New York University. His prior affiliations include the University of Chicago (2011–2013), the Georgia Institute of Technology (2004­–2007), and the Institute for Advanced Study (2003–2004). He has published numerous articles in scientific journals and conference proceedings, including Journal of the ACM, SIAM Journal on Computing, Proceedings of the Annual IEEE Symposium on Foundations of Computer Science, Proceedings of the Annual ACM Symposium on Theory of Computing, and Proceedings of the Annual IEEE Conference on Computational Complexity, among many others.