Sources: Quanta Magazine and Simons Foundation

Subash Khot is this year’s winner of the Nevanlinna Prize. If his “Unique Games Conjecture is correct, then for many of the problems people would most like to solve, it’s hard not only to find an exact solution—finding even a good approximation of the solution is beyond the reach of a computer. This conjecture may seem, on the face of it, like a pretty parochial statement (though possibly hard to prove, or even false). Over the past decade, however, computer scientists have found to their surprise that if the conjecture is true, then a host of problems—some of them seeming to bear little resemblance to the original Unique Games problem—are also hard to approximate.” Simons Foundation. 

Source: Quanta Magazine

“For the problem of coloring the nodes of a network that has a collection of constraints about which color combinations are allowed (top left), it is sometimes possible to find a coloring that satisfies all the constraints (top right). But for some networks and constraints (bottom left), it is impossible to satisfy all the constraints simultaneously. The Unique Games Conjecture concerns the problem of finding a coloring that satisfies as many constraints as possible, such as the bottom right coloring, which satisfies all the constraints except the one for the thick edge.” Quanta Magazine.