Two works regarding the Unique Games (UG) Conjecture

  1. A new point of NP-hardness for Unique Games by Ryan O'Donnell, John Wright
  2. Hypercontractivity, Sum-of-Squares Proofs, and their Applications by Boaz Barak, Aram W. Harrow, Jonathan Kelner, David Steurer, Yuan Zhou
See STOC'12 proceedings, May 20, 2012

Oded's comments

1) A new point of NP-hardness for Unique Games

The focus is on a (popular) special case of UG that consists of a system of linear equations in two variables modulo $q$. Let $2LIN(c,s)$ be the problem of finding an assignment that satisfies an $s$ fraction of the equations, when given a system for which a $c$ fraction of the equations can be satisfied. The standard UGC refers to points of the form $(1-\eps,\eps)$, where $\eps>0$ is arbitrary small (and $q$ grows as $poly(1/\eps)$). Hardness results were known before for the point $(3/4,11/16+\eps)$ (its extrapolation with the points $(0,0)$ and $(1,1)$) and a region close to $(0,0)$. The new hardness result is for $(1/2,3/8+\eps)$, which is obtained by using a result for $(1/2+1/2q,3/8+5/8q+\eps)$.

The new construction is based on constructing a special purpose PCP (rather than a test) for the standard "matching dictator problem". Specifically, the proof oracle is an auxiliary function $h$, and rather than testing the two functions against each other, one test one of the two functions versus $h$. Indeed, a lesson to take home is that, when constructing PCPs, one may always replace testers by special purpose PCPs (of proximity).

2) Hypercontractivity, Sum-of-Squares Proofs, and their Applications

Here $UG(\eps)$ is a special case of $2LIN(1-\eps,\eps)$ as in (1). The presentation focused on the first result of the paper, but I find the second one more interesting. Its starting point is that the subexponential-time algorithm of Arora, Barak, and Steurer [2010] is viewed as evidence against UGC, since it is said that NP-hard problems should be exponentially hard (wrt their "natural" parameter). Personally, I am not convinced by this evidence (*), and the foregoing result adds concreteness to my principled skepticism: It shows that there exists a natural generalization of UG that (i) has a subexponential time algorithm, and (ii) has no polynomial-time algorithm provided that SAT requires exponential time (i.e., the "ETH").

*) Firstly, a problem may be hard and not NP-hard; secondly, I don't see why all NP-hard problems should be exponentially hard (wrt some "natural" parameter), although some may be so; and thirdly I don't see what is fundamental in exponential-time (as opposed to the inevitability of exhaustive search). Lastly, I think that there is something fundamentally wrong in trying to infer more basic issues (i.e., intractability) based on more advanced ones (i.e., inevitability of exhaustive search)


Back to list of Oded's choices.