Hubbry Logo
Subhash KhotSubhash KhotMain
Open search
Subhash Khot
Community hub
Subhash Khot
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Subhash Khot
Subhash Khot
Subhash Khot
View on Wikipedia
from Wikipedia

Subhash Khot FRS (born 10 June 1978 in Ichalkaranji)[1] is an Indian-American mathematician and theoretical computer scientist who is the Julius Silver Professor of Computer Science in the Courant Institute of Mathematical Sciences at New York University. Khot has contributed to the field of computational complexity, and is best known for his unique games conjecture.[2]

Key Information

Khot received the 2014 Rolf Nevanlinna Prize by the International Mathematical Union and received the MacArthur Fellowship in 2016.[3] He was elected a Fellow of the Royal Society in 2017[4] and was inducted into the National Academy of Sciences in 2023.[5]

Education

[edit]

Khot obtained his bachelor's degree in computer science from the Indian Institute of Technology Bombay in 1999.[6] He received his doctorate degree in computer science from Princeton University in 2003 under the supervision of Sanjeev Arora. His doctoral dissertation was titled "New Techniques for Probabilistically Checkable Proofs and Inapproximability Results."[7]

Honours and awards

[edit]

Khot is a two time silver medallist representing India at the International Mathematical Olympiad (1994 and 1995).[8][9] Khot topped the highly difficult IIT JEE entrance exam in 1995.

He has been awarded the Microsoft Research New Faculty Fellowship Award (2005),[10] the Alan T. Waterman Award (2010), the Rolf Nevanlinna Prize for his work on the Unique Games Conjecture (2014), and the MacArthur Fellowship (2016).[11]

He was elected a Fellow of the Royal Society in 2017,[12] and was elected to the National Academy of Sciences in 2023.[13]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Subhash Khot

View on Grokipedia
from Grokipedia
Subhash Khot is an Indian-American theoretical computer scientist 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 Courant Institute of Mathematical Sciences, 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 Sanjeev Arora. 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 MacArthur 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, complexity theory, 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 Courant Institute of Mathematical Sciences 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 ϵ>0\epsilon > 0, there exists a sufficiently large integer k=k(ϵ)k = k(\epsilon) such that, given a unique game with kk labels per variable, it is NP-hard to distinguish between instances where there exists an assignment satisfying at least a 1−ϵ1 - \epsilon fraction of the constraints and instances where no assignment satisfies more than an ϵ\epsilon fraction of the constraints. Unique Game U=(G=(V,E),,{πe:→}e∈E),\text{Unique Game } U = (G=(V,E), , \{\pi_e : \to \}_{e \in E}), where GG is a bipartite graph, ={1,…,k} = \{1, \dots, k\} is the label set, and each πe\pi_e is a permutation ensuring uniqueness: for any labels xu,xv∈x_u, x_v \in , the constraint e=(u,v)e = (u,v) is satisfied if and only if xv=πe(xu)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ϵ)(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 αGW≈0.87856\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−ϵ2 - \epsilon for any constant ϵ>0\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 PCP constructions, including long-code tests and Fourier-analytic techniques, and in SDP 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 αGW+ϵ\alpha_{GW} + \epsilon for any ϵ>0\epsilon > 0. This result extends to other 2-variable CSPs, demonstrating optimal inapproximability under similar conditions and highlighting the limitations of SDP 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, Khot 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 PCP techniques to derive unconditional hardness results for Label Cover variants. Khot's influence is evident in his surveys on PCP-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. https://cs.nyu.edu/~khot/
  2. https://www.simonsfoundation.org/people/subhash-khot/
  3. https://cs.nyu.edu/dynamic/people/faculty/
  4. https://www.nasonline.org/directory-entry/subhash-a-khot-mnju1b/
  5. https://www.macfound.org/fellows/class-of-2016/subhash-khot
  6. https://www.nyu.edu/about/news-publications/news/2014/august/courants-khot-wins-rolf-nevanlinna-prize.html
  7. https://cs.nyu.edu/~khot/papers/UGCSurvey.pdf
  8. https://cims.nyu.edu/dynamic/news/790/
  9. https://cs.nyu.edu/dynamic/people/achievements/
  10. https://www.quantamagazine.org/a-grand-vision-for-the-impossible-20140812/
  11. https://www.census2011.co.in/census/city/385-ichalkaranji.html
  12. https://www.business-standard.com/article/news-ians/maths-nobel-winner-a-topper-all-his-life-114081400874_1.html
  13. https://www.wired.com/2014/08/subhash-khot-nevanlinna-prize/
  14. https://timesofindia.indiatimes.com/city/kolhapur/ichalkaranji-man-wins-maths-prize/articleshow/40250372.cms
  15. https://www.thehindu.com/news/national/Vyankatrao-High-School-cradle-of-a-Math-whiz/article60088423.ece
  16. https://www.imo-official.org/participant_r.aspx?id=920
  17. https://engineering.princeton.edu/news/2014/08/22/khot-wins-nevanlinna-prize-3rd-princeton-computer-science
  18. https://www.cs.princeton.edu/techreports/2003/673.pdf
  19. https://as.nyu.edu/faculty/subhash-khot.html
  20. https://paw.princeton.edu/article/tiger-week-subhash-khot-03
  21. https://www.thehindu.com/news/A-round-of-questions-with-Subhash-Khot/article60343716.ece
  22. https://mdpi-res.com/bookfiles/mono/11346/IMU_ICM_Medals_Prizes_and_Laureates.pdf
  23. https://dl.acm.org/doi/10.1145/509907.510017
  24. https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf
  25. https://www.cs.toronto.edu/~toni/Courses/PCP/handouts/ugc-vc.pdf
  26. https://arxiv.org/abs/2409.20028
  27. https://epubs.siam.org/doi/10.1137/S0097539705447372
  28. https://theoryofcomputing.org/articles/v021a002/
  29. https://cs.nyu.edu/~khot/papers/icm-2014.pdf
  30. https://www.eurekalert.org/news-releases/472176
  31. https://www.mathunion.org/imu-net/archive/2014/imu-net-066b
  32. https://awards.acm.org/award_winners/khot_8538828
  33. https://sloan.org/storage/app/media/files/annual_reports/2006_annual_report.pdf
  34. https://royalsociety.org/people/subhash-khot-13399/
Add your contribution
Related Hubs
User Avatar
No comments yet.