TR10-112 Authors: Subhash Khot, Dana Moshkovitz

Publication: 15th July 2010 16:39

Downloads: 1876

Keywords:

In this paper, we consider the problem of approximately solving a system of homogeneous linear equations over reals, where each

equation contains at most three variables.

Since the all-zero assignment always satisfies all the equations exactly, we restrict the assignments to be ``non-trivial". Here is

an informal statement of our result: it is NP-hard to distinguish whether there is a

non-trivial assignment that satisfies $1-\delta$ fraction of the

equations or every non-trivial assignment fails to satisfy a constant fraction of the equations with a ``margin" of $\Omega(\sqrt{\delta})$.

We develop linearity and dictatorship testing procedures for functions $f: \R^n \mapsto \R$ over a Gaussian space, which could be

of independent interest.

Our research is motivated by a possible approach to proving the Unique Games Conjecture.

This is a new and improved version of our paper that established the same result, but under the Unique Games Conjecture.