Hardness of Approximately Solving Linear Equations Over Reals.
Dana Moshkovitz, Subhash Khot · Electronic colloquium on computational complexity · 2010
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− δ fraction of the equations or every non-trivial assignment fails to satisfy a constant fraction of the equations with a “margin” of Ω( √ δ). We develop linearity and dictatorship testing procedures for functions f : R 7→ 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.