## 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 approximating Max-3SAT looks like this:
In other words, obtaining any approximation better than 7/8+o(1) takes (nearly-)exponential time, while obtaining (7/8)-approximation is polynomial (in fact, linear) time, due to a simple random setting algorithm. 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 coarse. In particular, it was open whether a sub-exponential time algorithm could be given for sufficiently loose constant approximation e<1/8. Our work eliminated these possibilities, and showed that the computational phase transition is sharp. Our work is applicable not just for Max-3SAT, but for all
of Håstad’s problems, and for many other problems. The
reason for the wide-applicability is that we provided an So we get better results for every problem whose NP-hardness of approximation is proven by composition of Raz’s verifier (aka Label-Cover/projection games hardness) with the long-code -- the mainstream method today to prove NP-hardness of approximation.
The main algebraic problem we considered was Fix a finite field F and natural numbers m and d, as well
as a function f:F The converse is also true – if the restriction of f to every line is a univariate polynomial of degree at most d, then f is an m-variate polynomial of degree at most d. The low degree testing theorem says that if the restriction of f to a small fraction of the lines is somewhat close to a univariate polynomial of degree at most d (i.e., there exists a univariate polynomial of degree at most d that agrees with f on a small fraction of the points in the line), then f must be close to an m-variate polynomial of degree at most d. Rubinfeld-Sudan initiated this study in the 1990’s, and the theorem was proven by Arora-Sudan, 1997 (a similar theorem was proven at around the same time by Raz-Safra). It is the main theorem that goes into the construction of algebraic PCPs. We
devised a small collection of constant-dimensional subspaces, of size |F |