Hardness of Approximately Solving Linear Equations Over Reals

Video of this lecture

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