Unique Games Conjecture – halfway there?

Windows On Theory 2018-03-12

Subhash Khot, Dor Minzer and Muli Safra just posted an exciting manuscript online. In it, they confirm the combinatorial hypothesis I’ve posted about before on the structure of non-expanding set in the degree two short-code graph (or, equivalently, in the Grassman graph). Together with their prior work with Dinur and Kindler, and a small assist of an expansion-to-testing reduction of Kothari, Steurer and I, this establishes (an imperfect completeness variant of) Khot’s two to one conjecture and the intermediate complexity conjecture. This also makes significant progress towards proving, or at least giving evidence for, the more famous unique games conjecture (UGC). In fact, as I explain below, there is a technical sense in which it goes “halfway” towards proving the UGC.

The Unique Games ( $UG(s,c)$ ) problem with parameters $0 \leq s \leq c \leq 1$ is the following: given a set of linear equations each involving at most two variables over some finite field, to distinguish between the completeness case where there exists an assignment to the variables satisfying at least $c$ fraction of the equations, and the soundness case where every assignment satisfies fewer than a $s$ fraction.

Clearly the $UG(s,c)$ problem becomes easier the larger the gap between $c$ and $s$ . The unique games conjecture is that the problem is as hard as it can be, in the sense that it is NP hard for $c$ arbitrarily close to one and $s$ arbitrarily close to zero (as a function of the field size which we assume tends to infinity in what follows). In other words, the difficulty of $UG(s,c)$ as a function of $c$ and $s$ is conjectured by the UGC to look like this:

ugc_fig1

(Note that the problem does not make sense when $c<s$ . Also, in this figure we ignore regions of measure zero. In particular for $c = 1-o(1)$ or $s=o(1)$ the problem can be solved by a semidefinite program where the precise $o(1)$ factors depend on the field size; it is known that if the UGC is true then this dependence is optimal.)

Until today, what was known about unique games could be summarized in this (not to scale) figure:

UGC_fig2

That is, when $s$ and $c$ are sufficiently close to each other, $UG(s,c)$ was known to be NP hard (see for example this paper) and in fact with a linear-blowup reduction establishing exponential hardness (i.e. $2^{\tilde{\Omega}(n)}$ under the exponential time hypothesis. On the other hand, when either the completeness parameter is sufficiently close to one or the soundness is sufficiently close to zero, there was a known subexponential time algorithm of Arora, Steurer and I (see also here) for $UG(s,c)$ . (That is, an algorithm running in time $2^{n^\xi}$ for some $\xi<1$ which tends to zero as either completeness tends to one or soundness tends to zero.)

However, that algorithm was of course only an upper bound, and we did not know whether it could be improved further to $2^{n^{o(1)}}$ or even polynomial time. Moreover, its mere existence showed that in some sense the techniques of the previously known NP hardness results for $UG(s,c)$ (which used a linear blow up reduction) are inherently inapplicable to establishing the UGC which requires hardness in a completely different regime.

The new result of Khot, Minzer and Safra (when combined with the prior ones) shows that $UG(s,c)$ is NP hard for $c$ arbitrarily close to half and $s$ arbitrarily close to zero. (The result is presented as hardness of 2 to 2 games with completeness close to one, but immediately implies hardness of unique games with completeness close to half.) That is, the new picture of unique games’ complexity is as follows:

ugc_fig3

This establishes for the first time hardness of unique games in the regime for which a sub-exponential time algorithm was known, and hence (necessarily) uses a reduction with some (large) polynomial blowup. While it is theoretically still possible for the unique games conjecture to be false (as I personally believed would be the case until this latest sequence of results) the most likely scenario is now that the UGC is true, and the complexity of the $UG(s,c)$ problem looks something like the following:

ugc_summary

That is, for every $0<s<c<1$ , the best running time is roughly $2^{n^{\xi(c,s)}}$ where $\xi:(0,1)^2 \rightarrow (0,1]$ is a function that is always positive but tends to zero as $c$ tends to one or $s$ tends to zero (and achieves the value one in a positive measure region of the plane). Of course we are still yet far from proving this, let alone characterizing this function, but this is still very exciting progress nonetheless.

I personally am also deeply interested in the question of whether the algorithm that captures this curve is the sum of squares algorithm. Since SoS does capture the known subexponential algorithms for unique games, the new work provides more evidence that this is the case.