$\mathcal{NP}$-Hardness of Approximately Solving Linear Equations over Reals
Subhash Khot, Dana Moshkovitz · SIAM Journal on Computing · 2013
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 “nontrivial.” Here is an informal statement of our result: it is $\mathcal{NP}$-hard to distinguish whether there is a nontrivial assignment that satisfies $1-\delta$ fraction of the equations or every nontrivial 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: \mathbb{R}^n \mapsto \mathbb{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.