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 |
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