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.
