# CSAIL Event Calendar: Previous Series

 Hardness of Approximately Solving Linear Equations Over Reals Speaker: Dana Moshkovitz , CSAIL, MITDate: September 7 2010 Time: 4:15PM to 5:15PM Location: 32-144Host: Scott Aaronson, CSAIL, MITContact: Be Blackburn , 3-6098, imbe@mit.eduWe 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/2011See other events happening in September 2010