Subhash Khot (born June 10, 1978 in Ichalkaranji) is an Indian-American

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...

and theoretical computer scientist who is the Julius Silver Professor of Computer Science in the Courant Institute of Mathematical Sciences at

New York University New York University (NYU) is a private research university in New York City. Chartered in 1831 by the New York State Legislature, NYU was founded by a group of New Yorkers led by then- Secretary of the Treasury Albert Gallatin. In 1832, ...

. Khot's unexpected and original contributions are providing critical insight into unresolved problems in the field of

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

. He is best known for his

unique games conjecture In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the approximate ''value'' of a certain type of ga ...

. Khot was awarded the 2014

Rolf Nevanlinna Prize The IMU Abacus Medal, known before 2022 as the Rolf Nevanlinna Prize, is awarded once every four years at the International Congress of Mathematicians, hosted by the International Mathematical Union (IMU), for outstanding contributions in Mathematic ...

by the International Mathematical Union. He received the MacArthur Fellowship in 2016 and was elected a

Fellow of the Royal Society Fellowship of the Royal Society (FRS, ForMemRS and HonFRS) is an award granted by the judges of the Royal Society of London to individuals who have made a "substantial contribution to the improvement of natural knowledge, including mathematic ...

in 2017.

Education

Early in his schooling days, as a

Marathi Marathi may refer to: *Marathi people, an Indo-Aryan ethnolinguistic group of Maharashtra, India *Marathi language, the Indo-Aryan language spoken by the Marathi people *Palaiosouda, also known as Marathi, a small island in Greece See also * * ...

-medium student, Khot was identified as a very bright student by Vyankatrao high school head master V. G. Gogate. He topped secondary and higher secondary school board exams as well. Khot topped the IIT-JEE exam and later obtained his bachelor's degree in

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...

from the

Indian Institute of Technology Bombay The Indian Institute of Technology Bombay (IIT Bombay or IITB) is a public research university and technical institute in Powai, Mumbai, Maharashtra, India. It is considered as one of the best engineering universities in India and is top ranke ...

in 1999. He received his doctorate degree in computer science from

Princeton University Princeton University is a private research university in Princeton, New Jersey. Founded in 1746 in Elizabeth as the College of New Jersey, Princeton is the fourth-oldest institution of higher education in the United States and one of the n ...

in 2003 under the supervision of

Sanjeev Arora Sanjeev Arora (born January 1968) is an Indian American theoretical computer scientist. Life He was a visiting scholar at the Institute for Advanced Study in 2002–03. In 2008 he was inducted as a Fellow of the Association for Computing Mac ...

. He also received an honorable mention in the ACM Doctoral Dissertation Award in 2003 for his dissertation, "New Techniques for Probabilistically Checkable Proofs and Inapproximability Results."

Honours and awards

Khot is a two time silver medalist representing India at the

International Mathematical Olympiad The International Mathematical Olympiad (IMO) is a mathematical olympiad for pre-university students, and is the oldest of the International Science Olympiads. The first IMO was held in Romania in 1959. It has since been held annually, except ...

in the years 1994 and 1995. In 1995, Khot topped the Indian Institute of Technology Joint Entrance Examination. In 2005, he received the Microsoft Research New Faculty Fellowship Award. The fellowship recognizes innovative, promising new faculty members who are exploring breakthrough, high-impact research that has the potential to help solve some of today's most challenging societal problems. In 2010, Khot received the

Alan T. Waterman Award The Alan T. Waterman Award, named after Alan Tower Waterman, is the United States's highest honorary award for scientists no older than 40, or no more than 10 years past receipt of their Ph.D. It is awarded on a yearly basis by the National Scienc ...

, which recognizes an early career scientist for their outstanding contributions in their respective field. The National Science Foundation citation for the Waterman award states: "For unexpected and original contributions to computational complexity, notably the Unique Games Conjecture, and the resulting rich connections and consequences in optimization, computer science and mathematics". Khot gave an invited talk at the International Congress of Mathematicians in 2010, on the topic of "Mathematical Aspects of Computer Science". Khot was awarded the 2014

by the International Mathematical Union, for his work related to the

Unique Games Conjecture In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the approximate ''value'' of a certain type of ga ...

, as well as for posing the conjecture itself. According to the International Mathematical Union citation, "he is awarded the Nevanlinna Prize for his prescient definition of the “Unique Games” problem, and leading the effort to understand its complexity and its pivotal role in the study of efficient approximation of optimization problems; his work has led to breakthroughs in algorithmic design and approximation hardness, and to new exciting interactions between computational complexity, analysis and geometry". Khot received the MacArthur Fellowship (or "Genius Grant") in 2016. The MacArthur foundation states that these are "unrestricted fellowships to talented individuals who have shown extraordinary originality and dedication in their creative pursuits and a marked capacity for self-direction". He was elected a Fellow of the Royal Society in 2017. Fellows are elected based on having made "a substantial contribution to the improvement of natural knowledge, including mathematics, engineering science and medical science".

References

{{DEFAULTSORT:Khot, Subhash 1978 births Living people Marathi people Princeton University alumni New York University faculty IIT Bombay alumni Theoretical computer scientists University of Chicago faculty International Mathematical Olympiad participants Nevanlinna Prize laureates American people of Indian descent 21st-century American mathematicians 21st-century Indian mathematicians Fellows of the Royal Society Simons Investigator People from Ichalkaranji MacArthur Fellows Indian American