We prove that MAX-3SAT can be approximated in polynomial time
within a factor 9/8 on random instances.
We survey the area of algebraic complexity theory; with the focus being on the problem of polynomial identity testing (PIT). We discuss the key ideas that have gone into the results of the last few years.
more >>>We reduce the problem of proving a "Boolean Unique Games Conjecture" (with gap $1-\delta$ vs. $1-C\delta$, for any $C> 1$, and sufficiently small $\delta>0$) to the problem of proving a PCP Theorem for a certain non-unique game.
In a previous work, Khot and Moshkovitz suggested an inefficient candidate reduction (i.e., ...
more >>>
