REPORTS > DETAIL:

### Paper:

TR10-053 | 28th March 2010 22:03

#### Hardness of Approximately Solving Linear Equations Over Reals

TR10-053
Authors: Dana Moshkovitz, Subhash Khot
Publication: 28th March 2010 22:09
Keywords:

Abstract:

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.

### Comment(s):

Comment #1 to TR10-053 | 15th July 2010 20:58

#### An improved version is available

Authors: Subhash Khot, Dana Moshkovitz
Accepted on: 15th July 2010 20:58
Keywords:

Comment:

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.

ISSN 1433-8092 | Imprint