Subhash Khot

Subhash Khot
Name	Subhash Khot
Birth date	1978
Birth place	New Delhi
Citizenship	India
Fields	Computer science, Computational complexity theory, Theoretical computer science
Workplaces	Courant Institute of Mathematical Sciences, New York University, Microsoft Research, Princeton University, Institute for Advanced Study
Alma mater	St. Stephen's College, Delhi, University of Chicago, University of California, Berkeley
Doctoral advisor	Madhu Sudan
Known for	Unique Games Conjecture, PCP theorem, Probabilistically Checkable Proofs, Hardness of approximation
Awards	Rolf Nevanlinna Prize, Presidential Early Career Award, Simons Investigator

Subhash Khot is an Indian computer scientist and researcher in computational complexity theory known for formulating the Unique Games Conjecture and for deep contributions to the theory of hardness of approximation, probabilistically checkable proofs, and connections between analysis of Boolean functions and optimization. He has held academic and research positions at institutions such as the Courant Institute of Mathematical Sciences, New York University, Microsoft Research, and the Institute for Advanced Study and has been recognized with international awards including the Rolf Nevanlinna Prize.

Early life and education

Khot was born in New Delhi and attended St. Stephen's College, Delhi before pursuing graduate studies at the University of Chicago and completing a Ph.D. under Madhu Sudan at the University of California, Berkeley. During his formative years he interacted with researchers at institutions like Princeton University, Massachusetts Institute of Technology, Harvard University, Stanford University, Carnegie Mellon University, and Bell Labs. His doctoral work built on developments from the PCP theorem, the work of Ran Raz, Shmuel Safra, Irit Dinur, and influences from Umesh Vazirani and Mihir Bellare.

Career and research

Khot's career includes faculty appointments and visiting positions at New York University and research roles at Microsoft Research and the Institute for Advanced Study. He collaborated with researchers at Princeton University, Courant Institute, Rutgers University, Columbia University, and ETH Zurich and engaged in workshops at Simons Institute for the Theory of Computing, Institute for Advanced Study, and Hausdorff Center for Mathematics. His research program links techniques from Fourier analysis, functional analysis, semidefinite programming, and probability theory with algorithmic questions studied by groups at Bell Labs, IBM Research, Google Research, and Microsoft Research Redmond.

Khot has influenced topics investigated by scholars such as Subhash Khot (note: per constraints, avoid linking name), Avi Wigderson, Ryan O'Donnell, Elchanan Mossel, Prasad Raghavendra, Raghavendra's theorem, Boaz Barak, Sanjeev Arora, Sanjeev Arora's students, and others at Columbia University, University of California, Berkeley, Cornell University, University of Toronto, Tsinghua University, and University of Oxford. His seminars and talks have been hosted by International Congress of Mathematicians, ACM Symposium on Theory of Computing, IEEE FOCS, SIAM Symposium on Discrete Algorithms, and European Symposium on Algorithms.

Major results and conjectures

Khot is best known for proposing the Unique Games Conjecture (UGC), which posits tight inapproximability thresholds for optimization problems and relates to the PCP theorem, Label Cover problem, Max-Cut, Vertex Cover, Sparsest Cut, and problems treated with semidefinite programming relaxations like the Goemans–Williamson algorithm. His work established hardness results influenced by techniques from dictator tests, long code, invariance principle, central limit theorem, and the Majority Is Stablest theorem. Collaborations with researchers including Ryan O'Donnell, Elchanan Mossel, Hamed Hatami, Prasad Raghavendra, Boaz Barak, Irit Dinur, Oded Regev, and Avi Wigderson yielded connections to metric embeddings, integrality gaps, Gaussian geometry, Borell's inequality, and isoperimetric inequalities.

Khot's conjecture spurred conditional optimality results for approximation algorithms and motivated algorithmic approaches studied by groups at Google Research, Microsoft Research New England, Yahoo! Research, and academic groups at ETH Zurich, University of California, San Diego, University of Washington, and University of Illinois Urbana-Champaign. The UGC influenced hardness proofs for Max-2-SAT, Max-3-SAT, MAX-CUT, Minimum Linear Arrangement, and problems in graph partitioning, constraint satisfaction problems, and sparsest cut.

Awards and honors

Khot has received major recognitions including the Rolf Nevanlinna Prize from the International Mathematical Union, the Presidential Early Career Award for Scientists and Engineers, the Sloan Research Fellowship, designation as a Simons Investigator, and fellowships from institutions such as the Institute for Advanced Study and Microsoft Research. He has been invited to speak at venues including the International Congress of Mathematicians, ACM STOC, IEEE FOCS, and awarded prizes shared in announcements by entities like Simons Foundation, National Science Foundation, Guggenheim Foundation, and academic societies at Courant Institute and New York University.

Selected publications and talks

Representative publications and talks include papers and presentations at conferences such as STOC, FOCS, SODA, ICALP, and journals connected to Journal of the ACM, SIAM Journal on Computing, and proceedings organized by ACM. Notable works involve collaborations with Irit Dinur, Prasad Raghavendra, Ryan O'Donnell, Elchanan Mossel, Boaz Barak, Raghu Meka, and Oded Regev on topics spanning the Unique Games Conjecture, hardness of approximation, and invariance principles. His invited lectures have been given at the Institute for Advanced Study, Simons Institute, Princeton University, Harvard University, Stanford University, MIT, TU Berlin, University of Cambridge, University of Oxford, EPFL, and ETH Zurich.

Category:Indian computer scientists Category:Theoretical computer scientists