Hardness of Approximately Solving Linear Equations Over Reals
Speaker: Dana Moshkovitz , CSAIL, MIT
Date: September 7 2010
Time: 4:15PM to 5:15PM
Location: 32-144
Host: Scott Aaronson, CSAIL, MIT
Contact: Be Blackburn , 3-6098, imbe@mit.edu
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". Here is an informal statement of our result: it is NP-hard to 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 \Omega(\sqrt{\delta}).
Unlike the well-studied case of linear equations over finite fields, for equations over reals, the best approximation algorithm known (SDP-based) is the same no matter whether the number of variables per equation is two or three.
Our result is motivated by the following potential approach to proving The Unique Games Conjecture:
1. Prove the NP-hardness of solving approximate linear equations over reals, for the case of three variables per equation (we prove this result).
2. Prove the NP-hardness of the problem for the case of two variables per equation, possibly via a reduction from the three variable case.
3. Prove the Unique Games Conjecture.
An interesting feature of our result is that it shows NP-hardness result that matches the performance of a non-trivial SDP-algorithm. Indeed, the Unique Games Conjecture predicts that an SDP-based algorithm is optimal for a huge class of problems (e.g. all constraint satisfaction problems by Raghavendra's result).
(This is joint work with Subhash Khot)
See other events that are part of Theory Colloquium 2010/2011
See other events happening in September 2010
