## My Post-DocSubhash Khot and I researched a certain approach for proving the Unique Games Conjecture. We proved an NP-hardness result for a problem on real equations which, we believe, might be useful as a starting point for a proof of the unique games conjecture.
x for large k, where all but at most d fraction of the equations can be satisfied simultaneously, it is NP-hard to find an assignment to the variables that satisfies even an e fraction of the equations. The equations are “unique” in the sense that an assignment to any one of the two variables appearing in an equation uniquely determines a satisfying assignment to the other variable. The conjecture was originally phrased for any unique tests, and not necessarily for linear equations with two variables per equation. However, the two formulations were shown to be equivalent by Khot, Kindler, Mossel and O’Donnell. Under the conjecture, one can prove tight NP-hardness of approximation for a large number of problems that otherwise do not have such proofs. Examples include Max-Cut, Vertex-Cover, and other problems where there are constraints posed on two variables at a time. Under the conjecture, a certain semi-definite programming based algorithm is optimal for any constraint satisfaction problem (Raghavendra, 2008).
a find a (non-trivial) assignment Specifically, assume that all but at most d fraction of the equations can be satisfied exactly by an assignment that is far from all-zero, find an assignment far from all-zero that approximately satisfies even just 0.9 fraction of the equations.
·
“Far from all-zero” means
that (sum x ·
“Approximate
satisfaction” means that |a A simple semi-definite programming based algorithm is able
to solve this problem with margin a=O(d We prove the NP-hardness of the approximate linear
equations problem for margin a=0.0001
d We suggest the following program for proving the Unique Games Conjecture: 1. Prove NP-hardness for q>2, which we did. 2. Prove NP-hardness for q=2, perhaps by reduction from step 1 – this is what we don’t know to do. 3. Apply parallel repetition to deduce the Unique Games Conjecture. This is relatively easy provided step 2. A few remarks about the construction for q>2: · The constraint graph induced on the variables is not an expander, which we know has to happen for hard unique games (this was proved by Arora, Khot, Kolla, Steurer, Tulsiani and Vishnoi, 2008). ·
The blow-up in the
reduction is n to n |

## My PhDRan Raz and I showed that approximating Max-3SAT and other problems exhibit a sharp phase-transition in their computational hardness. That is, if you assume (exact) 3SAT takes exponential-time
2 and the time complexity of achieving this approximation on the other axis, then the graph for Max-3SAT looks like this:
That is, obtaining any approximation better than 7/8+o(1) takes (nearly-)exponential time 2 Obtaining (7/8)-approximation is polynomial (in fact, linear) time, due to a simple random setting algorithm. And the drop from exponential time to polynomial time is By the work of Håstad in 1997,
it was known that any approximation better than 7/8+e of Max-3SAT for a This left open the possibility that the computational
threshold at 7/8 is Our work eliminates these possibilities, and shows that the computational phase transition is sharp. It does so not just for Max-3SAT, but for all of Håstad’s problems, and for many other problems (e.g., linear equations over finite fields). Our work offers an efficient alternative to Raz’s parallel repetition theorem, and thus it works for every problem whose NP-hardness of approximation is proven by composition of Raz’s verifier with the long-code. The latter method is today the mainstream method to prove NP-hardness of approximation, and so our results are widely applicable.
The main algebraic testing problem we considered was given a finite field F and
natural numbers m and d, as well as a function f:F One direction of this relation is relatively easy: if f
agrees with a degree d polynomial on a large fraction of the points in F The other direction is trickier: suppose that when
restricted to a noticeable fraction of the lines, the function f is close to
degree d. Does this mean that f is close to degree d on F In 1997, Arora and Sudan, as well as Raz and Safra, proved that this is indeed the case. The “global proximity” and the “local proximity” are essentially the same. This was after Sudan and Rubinfeld, and others, proved that for the case of local proximity close to 1. We
devised a small collection of constant-dimensional subspaces, of size |F |