ECCC-Report TR10-112https://eccc.weizmann.ac.il/report/2010/112Comments and Revisions published for TR10-112en-usThu, 15 Jul 2010 16:39:42 +0300
Paper TR10-112
| NP-Hardness of Approximately Solving Linear Equations Over Reals |
Subhash Khot,
Dana Moshkovitz
https://eccc.weizmann.ac.il/report/2010/112In 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.Thu, 15 Jul 2010 16:39:42 +0300https://eccc.weizmann.ac.il/report/2010/112