Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-112 | 15th July 2010 15:34

NP-Hardness of Approximately Solving Linear Equations Over Reals


Authors: Subhash Khot, Dana Moshkovitz
Publication: 15th July 2010 16:39
Downloads: 4468


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.

ISSN 1433-8092 | Imprint