Theory of Computing
-------------------
Title : On the Hardness of Approximating Balanced Homogenous 3-Lin
Authors : Johan Haastad and Rajsekar Manokaran
Volume : 13
Number : 10
Pages : 1-19
URL : http://www.theoryofcomputing.org/articles/v013a010
Abstract
--------
We consider systems of homogeneous linear equations modulo 2 with
three variables in each equation and study balanced assignments as
solutions to such equations. We prove that it is hard to distinguish
systems where there is a balanced assignment that satisfies a fraction
$1-\epsilon$ of the equations from systems where the best balanced
assignment satisfies a fraction $\frac 12 + \epsilon$ of the equations
assuming that NP is not contained in quasipolynomial time. This
improves on a similar result by Holmerin and Khot who relied on the
assumption that NP is not contained in subexponential time. The key
for the improvement is to replace long codes used by Holmerin and Khot
by the low-degree long code.