NP-Hardness of approximately solving linear equations over reals

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 NP-hard to distinguish whether there is a nontrivial assignment that satisfies 1-δ fraction of the equations or every nontrivial assignment fails to satisfy a constant fraction of the equations with a marginh of ω(√δ ). We develop linearity and dictatorship testing procedures for functions f : 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.