pdf icon
Volume 13 (2017) Article 10 pp. 1-19
On the Hardness of Approximating Balanced Homogenous 3-Lin
Received: November 18, 2014
Revised: May 18, 2017
Published: October 7, 2017
Download article from ToC site:
[PDF (322K)]    [PS (1465K)]    [PS.GZ (373K)]
[Source ZIP]
Keywords: hardness of approximation, inapproximability, probabilistically checkable proofs
ACM Classification: F.2.2, F.1.3
AMS Classification: 68Q17, 68Q25

Abstract: [Plain Text Version]

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.