Volume 13 (2017) Article 10 pp. 1-19
On the Hardness of Approximating Balanced Homogenous 3-Lin
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.