The Taub Faculty of Computer Science Events and Talks

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.