Theory Seminar: Hardness of Approximately Solving Linear Equations Over Reals

Dana Moshkovitz (MIT)

Wednesday, 19.1.2011, 12:20

Taub 401

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 ofvariables 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 variablesper 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 CSPs by Raghavendra's result).

This is joint work with Subhash Khot.

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 ofvariables 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 variablesper 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 CSPs by Raghavendra's result).

This is joint work with Subhash Khot.