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.