Subhash Khot
Encyclopedia
Subhash Khot is an Associate Professor at New York University. He is best known for his Unique games conjecture
.
Khot obtained his bachelor’s degree in Computer Science
from the Indian Institute of Technology Bombay
in 1999. He received his doctorate degree in computer science from Princeton University
in 2003 under the supervision of Prof. Sanjeev Arora
. He has made several contributions to computational complexity
and his research work is an interdisciplinary area drawing connections from Optimization, Computer science and mathematics.
In 2010, Khot received the prestigious Alan T. Waterman Award
, which recognizes an early career scientist for their outstanding contributions in their respective field. In addition to a medal, Waterman awardees also receive a grant of $500,000 for advanced research.. In 2005, he received the Microsoft Research New Faculty Fellowship Award.
Khot is a two time silver medalist in International Mathematics Olympiad during the years 1994 and 1995 . He stood first in the IIT-JEE 1995, the Joint Entrance Examination for admission to the IITs
.
Unique games conjecture
In computational complexity theory, the Unique Games Conjecture is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the value of a certain type of game, known as a unique game, has NP-hard algorithmic complexity...
.
Khot obtained his bachelor’s degree in Computer Science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
from the Indian Institute of Technology Bombay
Indian Institute of Technology Bombay
The Indian Institute of Technology Bombay , popularly known as IIT Bombay or IITB, is a public research university located in Powai, Mumbai...
in 1999. He received his doctorate degree in computer science from Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
in 2003 under the supervision of Prof. Sanjeev Arora
Sanjeev Arora
Sanjeev Arora is a theoretical computer scientist who is best known for his work on probabilistically checkable proofs and, in particular, the PCP theorem. He is currently the Charles C...
. He has made several contributions to computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
and his research work is an interdisciplinary area drawing connections from Optimization, Computer science and mathematics.
In 2010, Khot received the prestigious Alan T. Waterman Award
Alan T. Waterman Award
The Alan T. Waterman Award is the United States's highest honorary award for scientists no older than 35. It is awarded on a yearly basis by the National Science Foundation. In addition to the medal, the awardee receives a grant of $500,000 to be used for advanced scientific research at the...
, which recognizes an early career scientist for their outstanding contributions in their respective field. In addition to a medal, Waterman awardees also receive a grant of $500,000 for advanced research.. In 2005, he received the Microsoft Research New Faculty Fellowship Award.
Khot is a two time silver medalist in International Mathematics Olympiad during the years 1994 and 1995 . He stood first in the IIT-JEE 1995, the Joint Entrance Examination for admission to the IITs
Indian Institute of Technology Joint Entrance Examination
The Indian Institute of Technology Joint Entrance Examination is an annual college entrance examination in India. It is used as a sole criterion for the Indian Institutes of Technology as well as other institutes.The exam is conducted by the various IITs by a policy of rotation...
.