Computer Science/Discrete Mathematics Seminar II

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