Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR19-093 | 15th July 2019 04:19

#### Improved 3LIN Hardness via Linear Label Cover

TR19-093
Authors: Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari
Publication: 16th July 2019 04:10
We prove that for every constant $c$ and $\epsilon = (\log n)^{-c}$, there is no polynomial time algorithm that when given an instance of 3LIN with $n$ variables where an $(1 - \epsilon)$-fraction of the clauses are satisfiable, finds an assignment that satisfies at least $(\frac{1}{2} + \epsilon)$-fraction of clauses unless $\mathbf{NP} \subseteq \mathbf{BPP}$. The previous best hardness using a polynomial time reduction achieves $\epsilon = (\log \log n)^{-c}$, which is obtained by the Label Cover hardness of Moshkovitz and Raz [J. ACM, 57(5), 2010] followed by the reduction from Label Cover to 3LIN of Hastad [J. ACM, 48(4):798--859, 2001].