Subhash Khot

Subhash Khot is a Silver Professor of Computer Science at the Courant Institute of Mathematical Sciences, New York University (NYU). His research focuses on algorithms, computational complexity, and computational intractability, particularly in the areas of hardness of approximation, probabilistically checkable proofs (PCPs), and metric embeddings. He completed his Ph.D. at Princeton University under Sanjeev Arora in 2003, followed by postdoctoral work at the Institute for Advanced Study (IAS) and roles at Georgia Tech and the University of Chicago before joining NYU in 2007.

His research has produced groundbreaking results, including foundational contributions to the Unique Games Conjecture and its implications for approximation algorithms. He has authored numerous influential papers in top conferences like FOCS, STOC, and SODA, addressing topics ranging from PCPs to learning theory and algorithmic lower bounds. His work has been recognized with awards such as the Best Paper Award at FOCS 2004 and 2005, and the Best Student Paper Award at Complexity 2003.

Khot has taught courses on algorithms, computational complexity, and theory of computation at NYU, Georgia Tech, and the University of Chicago. His teaching emphasizes algorithm design, NP-completeness, and advanced topics like geometric methods in algorithm design. He has advised multiple students through his research and courses, contributing to the education of future computer scientists.

His research also explores applications of computational complexity to areas like metric embeddings, learning theory, and concrete lower bounds in communication complexity. Khot’s work bridges theoretical computer science with practical algorithm design, making him a leading figure in computational theory.