Subhash Khot

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.

Description in a few paragraphs:
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.