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

by Subhash Khot and Dana Moshkovitz

#### Oded's comments

I feel unqualified to comment on the speculation stated in Sec 1.5,
by which the current work may lead
to establishing the Unique Game Conjecture (UGC).
Certainly, such a (candid) speculation is very intriguing.
Moving to more solid grounds, I wish to highlight two points that
are stated in Sec 1.2.
Firstly, that this work shows a case where
the SDP is on the one hand seemingly optimal
(under $P\neq NP$ and not under UGC),
and on the other hand outperforms trivial algorithms.
Secondly, this work demonstrates a gap between approximating
the square-L2 norm and approxmating the L1 norm.

Paper posted on ECCC
as TR10-112.

#### The original 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:
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\to\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.

Back to
list of Oded's choices.