| Awards |
 |
|
|
|
|
|
|
|
| Home > Awards > 2014 Awards |
|
|
| |
 Nevanlinna Prize Winner |
| |
|
| This video is provided by IMU and Simons Foundation. |
|
| |
 |
| Subhash Khot |
|
New York University, USA
[Subhash Khot is awarded the Nevanlinna Prize]
for his prescient definition of the “Unique Games” problem, and his leadership in the effort to understand its complexity and its pivotal role in the study of efficient approximation of optimization problems, have produced breakthroughs in algorithmic design and approximation hardness, and new exciting interactions between computational complexity, analysis and geometry.
|
|
|
| |
| • |
Subhash Khot defined the “Unique Games” in 2002 , and subsequently led the effort to understand its complexity and its pivotal role in the study of optimization problems. Khot and his collaborators demonstrated that the hardness of Unique Games implies a precise characterization of the best approximation factors achievable for a variety of NP-hard optimization problems. This discovery turned the Unique Games problem into a major open problem of the theory of computation. |
|
| |
| • |
The ongoing quest to study its complexity has had unexpected benefits. First, the reductions used in the above results identified new problems in analysis and geometry, invigorating analysis of Boolean functions, a field at the interface of mathematics and computer science. This led to new central limit theorems, invariance principles, isoperimetric inequalities, and inverse theorems, impacting research in computational complexity, pseudorandomness, learning and combinatorics. Second, Khot and his collaborators used intuitions stemming from their study of Unique Games to yield new lower bounds on the distortion incurred when embedding one metric space into another, as well as constructions of hard families of instances for common linear and semi- definite programming algorithms. This has inspired new work in algorithm design extending these methods, greatly enriching the theory of algorithms and its applications. |
|
| |
| |
| |
|
|
|
| |
|
|
|
|
| |
Copyrights ⓒ 2010-2015 International Congress of Mathematicians 2014 All right Reserved.
The Korea Science and Technology Center 710 New Bldg., 635-4 Yeoksam-dong, Gangnam-gu, Seoul 135-703, Republic of Korea |
|
| Tel: +82-2-563-2014 Fax: +82-2-563-2022 E-mail: icm@icm2014.org Homepage: www.icm2014.org |
|
|
| |
|
