TR10-053 Authors: Dana Moshkovitz, Subhash Khot

Publication: 28th March 2010 22:09

Downloads: 1572

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: assuming the Unique Games

Conjecture, 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.

Subsequently to this work, we established the NP-hardness of the same problem (without assuming the Unique Games Conjecture). This appears as ECCC TR10-112.