Fact-checked by Grok 2 weeks ago

Subhash Khot

Subhash Khot is an Indian-American renowned for his foundational work in , particularly for formulating the Unique Games Conjecture (UGC) in 2002, which posits significant limitations on approximation algorithms for NP-hard optimization problems and has profoundly influenced research in algorithms, hardness of approximation, and related mathematical areas. He is the Silver Professor of at New York University's , where his research explores connections between , , , and geometry to understand the inherent difficulties of computational tasks. Khot earned a B.Tech. in from the Indian Institute of Technology Bombay in 1999 and a Ph.D. in from in 2003 under the supervision of . Following his doctorate, he held a postdoctoral position at the Institute for Advanced Study from 2003 to 2004, served as an assistant professor at the Georgia Institute of Technology from 2004 to 2007, and joined NYU in 2007, advancing to full professor and eventually Silver Professor. His career also included a visiting faculty role at the from 2011 to 2013. Khot's contributions, especially the UGC—later surveyed in depth—have earned him numerous prestigious honors, including the Rolf Nevanlinna Prize from the in 2014 for advancing the understanding of NP-hard problems through probabilistically checkable proofs and approximation hardness. Other accolades include the Alan T. Waterman Award from the in 2010, recognizing his early-career impact on ; the Fellowship in 2016 for providing critical insights into unresolved problems in the field; the FOCS Test of Time Award in 2024; election as a in 2017; and induction into the in 2023. He also received the New Faculty Fellowship in 2005 and an honorable mention for the ACM Doctoral Dissertation Award in 2003.

Early life and education

Early life

Subhash Khot was born on June 10, 1978, in , a city of approximately 400,000 people (2025 est.) in , . He grew up in a middle-class family of medical professionals; his father, Ajit Khot, was an ear, nose, and throat specialist who passed away from a heart attack in 1995, while his mother, Jaishree Khot, is a based in . Khot has a brother, Amol, who is also a medical practitioner in . From an early age, Khot displayed a strong aptitude for , participating in national-level competitions that highlighted his talent. While attending Vyankatrao High School in , a Marathi-medium , he excelled academically and topped his class, particularly in , under the guidance of influential teachers like headmaster V. G. Gogate. Khot's prowess led to his selection for the , where he earned silver medals representing in 1994 in and in 1995 in , , achieving scores of 31 and 32 out of 42, respectively. These accomplishments, earned during his high school years, underscored his early dedication to mathematical problem-solving. Following high school, he transitioned to higher education at the Indian Institute of Technology Bombay.

Education

Subhash Khot earned a Bachelor of Technology (B.Tech.) degree in Computer Science from the Indian Institute of Technology Bombay in 1999. During his undergraduate years at IIT Bombay, Khot gained early exposure to theoretical computer science, gravitating toward its mathematical foundations and theorem-proving aspects rather than practical programming. Following his bachelor's degree, Khot pursued graduate studies in the United States, obtaining a Ph.D. in Computer Science from Princeton University in 2003. His doctoral advisor was Sanjeev Arora, a prominent researcher in approximation algorithms and complexity theory. Khot's Ph.D. thesis, titled New Techniques for Probabilistically Checkable Proofs and Inapproximability Results, focused on advancing approximation algorithms through connections to the Probabilistically Checkable Proofs (PCP) theorem. This work built on his undergraduate interests and laid foundational insights into computational hardness.

Academic career

Early positions

Following the completion of his Ph.D. in computer science from Princeton University in 2003, Subhash Khot took up a postdoctoral position as a Member in the School of Mathematics at the Institute for Advanced Study (IAS) in Princeton, New Jersey, from 2003 to 2004. This fellowship provided an environment for focused theoretical research, building directly on his doctoral work in computational complexity. In 2004, Khot transitioned to his first faculty role as an in the College of Computing at the Georgia Institute of Technology, where he served until 2007. In this position, he assumed initial academic responsibilities typical of an early-career faculty member, including teaching graduate and undergraduate courses on algorithms, , and related topics in . Additionally, Khot received an NSF award focused on inapproximability and probabilistically checkable proofs. Having relocated to the from in 1999 to begin his graduate studies at Princeton, Khot adapted to the American academic landscape through his Ph.D. training and subsequent roles, navigating differences in research collaboration, funding mechanisms, and pedagogical approaches in U.S. institutions. This period marked the foundational phase of his independent career in the U.S., emphasizing the shift from structured Indian technical education to the more interdisciplinary and grant-driven environment of American academia.

Positions at New York University

In 2007, Subhash Khot joined the at as an of . This appointment marked a significant step in his academic career following his tenure as an at the Georgia from 2004 to 2007, which provided foundational experience in . In 2011, Khot was promoted to full Professor at NYU, though he subsequently held a visiting faculty position in the theory group at the from 2011 to 2013. Upon his return to NYU in 2013, he resumed his role as Professor, continuing to contribute to the department's focus on and algorithms. In 2016, Khot was appointed the Julius Silver Professor of Computer Science, recognizing his distinguished contributions to the field. As of 2025, he holds this endowed chair at the Courant Institute, where he directs a research group exploring advanced topics in theoretical computer science.

Research contributions

Unique Games Conjecture

The Unique Games Conjecture (UGC), introduced by Subhash Khot in 2002 as part of his Ph.D. thesis at Princeton University, asserts the inapproximability of a restricted class of two-prover one-round games known as unique games. These games generalize constraint satisfaction problems (CSPs) where each constraint uniquely determines the labels on the involved variables, making them a pivotal test case for hardness in approximation algorithms. Khot formulated the UGC to bridge gaps in understanding the computational complexity of NP-hard optimization problems, building directly on foundational results in probabilistically checkable proofs (PCPs), such as the interactive proof characterizations by Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy, and subsequent hardness amplifications for Label Cover problems. Later refinements, including Irit Dinur's streamlined PCP theorem, further contextualized the UGC within the evolving framework of proof verification systems. Formally, the UGC states: For every \epsilon > 0, there exists a sufficiently large integer k = k(\epsilon) such that, given a unique game with k labels per variable, it is NP-hard to distinguish between instances where there exists an assignment satisfying at least a $1 - \epsilon fraction of the constraints and instances where no assignment satisfies more than an \epsilon fraction of the constraints. \text{Unique Game } U = (G=(V,E), , \{\pi_e : \to \}_{e \in E}), where G is a bipartite graph, = \{1, \dots, k\} is the label set, and each \pi_e is a permutation ensuring uniqueness: for any labels x_u, x_v \in , the constraint e = (u,v) is satisfied if and only if x_v = \pi_e(x_u). This hardness assumption implies that no polynomial-time algorithm can reliably solve even this specialized CSP to within a (1 - 2\epsilon)-approximation factor. The UGC has profound implications for the approximability of several NP-hard problems, providing tight hardness thresholds that match the performance of state-of-the-art algorithms. For Max-Cut, assuming the UGC, it is NP-hard to approximate the problem within a factor strictly better than the Goemans-Williamson constant \alpha_{GW} \approx 0.87856, the integrality gap of the (SDP) relaxation, thereby resolving the optimality of this long-standing result. For , the conjecture implies that no polynomial-time algorithm can approximate the minimum within a factor of $2 - \epsilon for any constant \epsilon > 0, aligning with the ratio achieved by the simple and closing a major open question in approximation complexity. These results extend to other CSPs, such as sparsest cut and balanced separator, establishing optimal inapproximability under the UGC framework. As of 2025, the UGC remains unresolved, neither proven nor refuted, despite extensive efforts to tackle it through algebraic, geometric, and methods. Nevertheless, it has catalyzed advancements in constructions, including long-code tests and Fourier-analytic techniques, and in hierarchies, such as sum-of-squares relaxations, which have yielded improved algorithms and partial resolutions for related problems even without assuming the full . Recent extensions, like quantum variants of unique games, continue to explore its boundaries, underscoring its enduring influence on .

Other work in computational complexity

Khot has made significant contributions to the inapproximability of problems (CSPs) through reductions that establish tight hardness bounds for various maximization problems. Assuming the UGC, Khot and collaborators showed that it is NP-hard to approximate Max-Cut within a factor strictly better than \alpha_{GW} + \epsilon for any \epsilon > 0. This result extends to other 2-variable CSPs, demonstrating optimal inapproximability under similar conditions and highlighting the limitations of relaxations for these problems. In the area of small-set expansion, Khot's work explores the expansion properties of specific graph families and their implications for computational hardness. He proved that in the Johnson graph, any small set of vertices either exhibits near-perfect edge expansion or correlates strongly with "pseudorandom" sets defined by low-influence functions, providing a of non-expanding sets. This connects to the expander mixing lemma by showing that such sets violate mixing properties only when aligned with coordinate-based dictatorships, advancing techniques for analyzing graph expansion in high-dimensional spaces. Through collaborative efforts, developed key reductions from Label Cover to establish hardness for a range of optimization problems, including sparsest cut and closest vector problems, showing inapproximability factors up to polylogarithmic in the input size. These reductions preserve gap instances and extend techniques to derive unconditional hardness results for Label Cover variants. 's influence is evident in his surveys on -based hardness, where he exposits the progression from the to advanced inapproximability results, emphasizing the role of and noise stability in deriving optimal bounds for CSPs.

Awards and honors

Major prizes

Subhash Khot received the Alan T. Waterman Award from the in 2010, the agency's highest honor for an early-career researcher under the age of 35. This prize recognizes outstanding contributions to science and engineering supported by the NSF, and Khot was specifically honored for his groundbreaking work in , particularly the , which has advanced the understanding of computational intractability in optimization problems. The award included a grant of $500,000 over three years to support his research. In 2014, Khot was awarded the Rolf Nevanlinna Prize by the , one of the highest distinctions in the mathematical aspects of , presented quadrennially at the . The prize citation commended his prescient definition of the Unique Games problem and his leadership in exploring its implications for the of in optimization tasks, fostering new connections between , , and . This recognition highlighted the conjecture's role in establishing barriers to efficient algorithms for NP-hard problems. Khot was named a MacArthur Fellow in 2016, receiving the prestigious "genius grant" for his exceptional creativity and potential to advance . The fellowship acknowledged his innovative approaches to unresolved questions in optimization and approximation, notably through the , which posits the NP-hardness of approximating certain problems and has spurred breakthroughs in related fields like and . The no-strings-attached award provided $625,000 over five years to support his ongoing work on fundamental limits of computation, including ties to the .

Fellowships and memberships

In 2003, Khot received an honorable mention for the ACM Doctoral Dissertation Award. In 2005, Khot received the Microsoft Research New Faculty Fellowship, a prestigious award supporting early-career faculty in computer science by providing funding for independent research initiatives. In 2006, Khot received the Sloan Research Fellowship. Khot was elected a in 2017, recognizing his outstanding contributions to science and joining an elite group of international scholars. In 2023, he was inducted into the as a member, honoring his significant advancements in .

References

  1. [1]
    Subhash Khot - NYU Computer Science
    I am a Professor in the Computer Science Department at New York University, part of the Courant Institute of Mathematical Sciences.
  2. [2]
    Subhash Khot - Simons Foundation
    In 2014, he was awarded the Rolf Nevanlinna Prize from the International Mathematical Union for his work on unique games conjecture. Khot's research is ...Missing: biography | Show results with:biography
  3. [3]
    Tenure-Track Faculty - NYU Computer Science Department
    Subhash Khot. Silver Professor of Computer Science. Ph.D., Computer Science, Princeton University, USA, 2003. Email: khot at cs.nyu.edu. Office: WWH 416. Ext: 8 ...All Research Areas · Machine Learning · Visiting Faculty · Faculty Fellows
  4. [4]
    Subhash A. Khot – NAS - National Academy of Sciences
    Khot received the NSF Alan T. Waterman Award in 2010, the Rolf Nevanlinna Prize from the International Mathematical Union in 2014, and the MacArthur Fellowship ...
  5. [5]
    Subhash Khot - MacArthur Foundation
    Sep 22, 2016 · Subhash Khot received a B.Tech. (1999) from the Indian Institute of Technology, Bombay, and a Ph.D. (2003) from Princeton University. He is ...
  6. [6]
    Courant's Khot Wins Rolf Nevanlinna Prize - NYU
    Aug 13, 2014 · Subhash Khot, a professor in NYU's Courant Institute of Mathematical Sciences, has been awarded the Rolf Nevanlinna Prize for 2014.Missing: biography | Show results with:biography
  7. [7]
    [PDF] On the Unique Games Conjecture - NYU Computer Science
    This article surveys recently discovered connections between the Unique Games Conjec- ture and computational complexity, algorithms, discrete Fourier analysis, ...
  8. [8]
    Subhash Khot wins NSF's Waterman Award - News | NYU Courant
    We are delighted to announce that Subhash Khot has received the extremely prestigious Alan T. Waterman Award. This award is given annually by NSF to an ...
  9. [9]
    A Grand Vision for the Impossible | Quanta Magazine
    Aug 12, 2014 · Subhash Khot's bold conjecture is helping mathematicians explore the precise limits of computation.Missing: American | Show results with:American
  10. [10]
    Maths 'Nobel' winner a topper all his life - Business Standard
    Aug 14, 2014 · Khot was a student at the Marathi medium school in the secondary section between 1987-1993 - and was the brightest in all spheres of academics, ...Missing: background parents
  11. [11]
    What It Takes to Win the World's Highest Computer Science Honor
    Aug 14, 2014 · Khot was awarded the 2014 Rolf Nevanlinna Prize, widely considered one of the top honors in his field.Missing: biography | Show results with:biography
  12. [12]
    Ichalkaranji man wins maths prize | Kolhapur News - Times of India
    Aug 14, 2014 · Subhash Khot, professor at the computer science ... principal of Vyankatrao high school, Ichalkaranji, where Khot completed his schooling.Missing: background parents
  13. [13]
    Vyankatrao HS – cradle of a Math whiz - The Hindu
    Aug 15, 2014 · Subhash Khot showed remarkable conceptual clarity, intense focus at an early age, says his former school principal.
  14. [14]
    Subhash Ajit Khot - International Mathematical Olympiad
    Rel. 1995 · India, 7, 7, 4, 7, 7, 0, 32, 66, 84.18%, Silver medal. 1994 · India, 7, 7, 7, 7, 2, 1, 31, 78, 79.95%, Silver medal ...
  15. [15]
    Khot wins Nevanlinna Prize; 3rd for Princeton computer science
    Aug 22, 2014 · Subhash Khot, who earned a Ph.D. from Princeton's Department of Computer Science in 2003, has won the Rolf Nevanlinna Prize.
  16. [16]
    [PDF] NEW TECHNIQUES FOR PROBABILISTICALLY CHECKABLE ...
    I am forever indebted to my advisor Sanjeev Arora for shaping every aspect of my academic life. ... Finally, my mom and my brother Amol, they mean everything to ...
  17. [17]
    Subhash Khot - NYU Arts & Science
    Professor Khot's specialty is computational complexity. This studies the inherent difficulty of computational tasks, attempting to determine which computational ...Missing: page | Show results with:page
  18. [18]
    Tiger of the Week: Subhash Khot *03 - Princeton Alumni Weekly
    Mar 17, 2010 · Last week, the National Science Foundation selected Subhash Khot *03 to receive the Alan T. Waterman Award, a prestigious grant of $500,000 ...<|control11|><|separator|>
  19. [19]
    A round of questions with Subhash Khot - The Hindu
    Sep 20, 2014 · This year, the International Mathematical Union awarded the Rolf Nevanlinna prize to Subhash Khot, Professor of computer science at New York ...
  20. [20]
    https://paw.princeton.edu/article/tiger-week-subhash-khot-03
  21. [21]
    On the power of unique 2-prover 1-round games - ACM Digital Library
    A 2-prover game is called unique if the answer of one prover uniquely determines the answer of the second prover and vice versa.
  22. [22]
    [PDF] Optimal Inapproximability Results for MAX-CUT and Other 2 ...
    Sep 19, 2005 · The proof of this hardness result relies on the Unique Games Conjecture of Khot [36]. We also rely critically on a theorem we call Majority ...
  23. [23]
    [PDF] Vertex Cover Might be Hard to Approximate to within 2 − ε
    He also observed that a variant of his conjecture would imply a √2 − ε hardness result for vertex cover. In this paper, we continue this line of research and, ...
  24. [24]
    [2409.20028] A Quantum Unique Games Conjecture - arXiv
    Sep 30, 2024 · In this work, we introduce definitions for the quantum extensions of Label-Cover and Unique-Label-Cover. We show that these problems play a similarly crucial ...Missing: 2025 | Show results with:2025
  25. [25]
    Optimal Inapproximability Results for MAX‐CUT and Other 2 ...
    Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs? Authors: Subhash Khot, Guy Kindler, ...
  26. [26]
    Small Set Expansion in the Johnson Graph - Theory of Computing
    The goal of this paper is to investigate small-set expansion properties of the Johnson graph, which is not a small-set expander.
  27. [27]
    [PDF] On the Optimality of Semidefinite Relaxations for Average-Case and ...
    Nov 21, 2012 · This work studies several questions about the optimality of semidefinite programming (SDP) for constraint satisfaction problems (CSPs). First we ...<|control11|><|separator|>
  28. [28]
    [PDF] Hardness of Approximation - NYU Computer Science
    The conjecture concerns the computational complexity of the small set expansion problem which, given a graph, asks for a small (but still of linear size) ...Missing: sparse Label
  29. [29]
    NSF selects young theoretical computer scientist for its highest honor
    Mar 9, 2010 · NYU's Subhash Khot named NSF's 2010 recipient of its Alan T. Waterman Award. Grant and Award Announcement. U.S. National Science Foundation.Missing: Georgia | Show results with:Georgia<|control11|><|separator|>
  30. [30]
    Special Issue on IMU Prizes and Medals at ICM 2014 in Seoul
    ROLF NEVANLINNA PRIZE (honoring distinguished achievements in mathematical aspects of information science):. - Subhash Khot of New York University (USA) for ...
  31. [31]
    IMO 1994: Rank 23/385 - International Mathematical Olympiad
    Silver medal. Leandro Saita · Argentina, 2, 7, 6, 7, 7, 7, 36, 44, Silver medal ... Subhash Ajit Khot · India, 7, 7, 7, 7, 2, 1, 31, 78, Silver medal. Sambuddha ...
  32. [32]
    Professor Subhash Khot FRS - Fellow Detail Page | Royal Society
    Subhash Khot is a theoretical computer scientist whose unexpected and original contributions are providing critical insight into unresolved problems.