# Hardness of Approximately Solving Linear Equations Over Reals

 COMPUTER SCIENCE/DISCRETE MATH II Topic: Hardness of Approximately Solving Linear Equations Over Reals Speaker: Dana Moshkovitz Affiliation: Member, School of Mathemtics Date: Tuesday, April 27 Time/Room: 10:30am - 12:30pm/S-101 Video Link: https://video.ias.edu/csdm/solvoverreals

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". We prove the hardness of the following problem: 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 sqrt{delta} . The hardness result matches the performance of a natural semi-definite programming-based algorithm. To prove our result, we develop linearity and dictatorship testing procedures for functions f:R^n |---> 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