### Subhash Khot’s prizewinning research

Saturday, August 16th, 2014I already congratulated Subhash Khot in my last post for winning the Nevanlinna Award, but this really deserves a separate post. Khot won theoretical computer science’s highest award largely for introducing and exploring the Unique Games Conjecture (UGC), which says (in one sentence) that a large number of the approximation problems that no one has been able to prove NP-hard, really *are* NP-hard. In particular, if the UGC is true, then for MAX-CUT and dozens of other important optimization problems, no polynomial-time algorithm can always get you closer to the optimal solution than some semidefinite-programming-based algorithm gets you, unless P=NP. The UGC might or might not be true—unlike with (say) P≠NP itself, there’s no firm consensus around it—but even if it’s false, the effort to prove or disprove it has by now had a huge impact on theoretical computer science research, leading to connections with geometry, tiling, analysis of Boolean functions, quantum entanglement, and more.

There are a few features that make the UGC interesting, compared to most other questions considered in complexity theory. Firstly, the problem that the UGC asserts is NP-hard—basically, given a list of linear equations in 2 variables each, to satisfy as many of the equations as you can—is a problem with “imperfect completeness.” This means that, if you just wanted to know whether *all* the linear equations were simultaneously satisfiable, the question would be trivial to answer, using Gaussian elimination. So the problem only becomes interesting once you’re told that the equations are *not* simultaneously satisfiable, but you’d like to know (say) whether it’s possible to satisfy 99% of the equations or only 1%. A second feature is that, because of the 2010 work of Arora, Barak, and Steurer, we know that there *is* an algorithm that solves the unique games problem in “subexponential time”: specifically, in time exp(n^{poly(δ)}), where δ is the completeness error (that is, the fraction of linear equations that are unsatisfiable, in the case that most of them are satisfiable). This doesn’t mean that the unique games problem can’t be NP-hard: it just means that, if there *is* an NP-hardness proof, then the reduction will need to blow up the instance sizes by an n^{poly(1/δ)} factor.

To be clear, neither of the above features is *unique* (har, har) to unique games: we’ve long known NP-complete problems, like MAX-2SAT, that have the imperfect completeness feature, and we also know NP-hardness reductions that blow up the instance size by an n^{poly(1/δ)} factor for inherent reasons (for example, for the Set Cover problem). But perhaps nothing points as clearly as UGC at the directions that researchers in hardness of approximation and probabilistically checkable proofs (PCP) would like to be able to go. A proof of the Unique Games Conjecture would basically be a PCP theorem on steroids. (Or, since we already have “PCP theorems on steroids,” maybe a PCP theorem on PCP?)

It’s important to understand that, between the UGC being true and the unique games problem being solvable in polynomial time, there’s a wide range of intermediate possibilities, many of which are being actively investigated. For example, the unique games problem could be “NP-hard,” but via a reduction that itself takes subexponential time (i.e., it could be hard assuming the Exponential-Time Hypothesis). It could be solvable much faster than Arora-Barak-Steurer but still not in P. Or, even if the problem weren’t solvable any faster than is currently known, it could be “hard without being NP-hard,” having a similar status to factoring or graph isomorphism. Much current research into the UGC is focused on a particular algorithm called the Sum-of-Squares algorithm (i.e., the Laserre hierarchy). Some researchers suspect that, if *any* algorithm will solve the unique games problem in polynomial time (or close to that), it will be Sum-of-Squares; conversely, if one could show that Sum-of-Squares failed, one would’ve taken a major step toward proving the UGC.

For more, I recommend this *Quanta* magazine article, or Luca Trevisan’s survey, or Subhash’s own survey. Or those pressed for time can simply check out this video interview with Subhash. If you’d like to try my wife Dana’s puzzle games inspired by PCP, which Subhash uses 2 minutes into the video to explain what he works on, see here. Online, interactive versions of these puzzle games are currently under development. Also, if you have questions about the UGC or Subhash’s work, go ahead and ask: I’ll answer if I can, and otherwise rely on in-house expertise.

Congratulations again to Subhash!