Subhash Khot, Silver Professor of Computer Science at the Courant Institute of Mathematical Sciences, has received a US$625,000 MacArthur Fellowship. Khot works in computational complexity theory and is known for his Unique Games Conjecture (UGC), which states that determining the approximate value of a certain type of game is NP-hard. Attempts to prove the conjecture have led to theorems in several areas of mathematics. (Photo: John D. & Catherine T. MacArthur Foundation.) From the news release issued by the MacArthur Foundation: "Work by Khot and others has demonstrated that although it is as yet unproven, the conjecture sheds new light on the computational complexity of many, very diverse, optimization tasks. If true, then solutions to a host of problems, many of them seemingly unrelated to the original problem of the UGC, are also too hard to approximate."
For more detail, see here http://www.ams.org/news?news_id=3178
Source: http://www.ams.org/
(Ngạch nghiên cứu viên)