A seminal result of H\r{a}stad [J. ACM, 48(4):798--859, 2001] shows that it is NP-hard to find an assignment that satisfies $\frac{1}{|G|}+\varepsilon$ fraction of the constraints of a given $k$-LIN instance over an abelian group, even if there is an assignment that satisfies $(1-\varepsilon)$ fraction of the constraints, for any constant $\varepsilon>0$. Engebretsen, Holmerin and Russell [Theoretical Computer Science, 312(1):17--45, 2004] later showed that the same hardness result holds for $k$-LIN instances over any finite non-abelian group.

Unlike the abelian case, where we can efficiently find a solution if the instance is satisfiable, in the non-abelian case, it is NP-complete to decide if a given system of linear equations is satisfiable or not, as shown by Goldmann and Russell [Information and Computation, 178(1):253--262, 2002].

Surprisingly, for certain non-abelian groups $G$, given a satisfiable $k$-LIN instance over $G$, one can in fact do better than just outputting a random assignment using a simple but clever algorithm. The approximation factor achieved by this algorithm varies with the underlying group. In this paper, we show that this algorithm is {\em optimal} by proving a tight hardness of approximation of satisfiable $k$-LIN instance over {\em any} non-abelian $G$, assuming $P \neq NP$. As a corollary, we also get $3$-query probabilistically checkable proofs with perfect completeness over large alphabets with improved soundness.

Our proof crucially uses structural properties captured by Gowers’ notion of {\em quasi-randomness} for non-abelian groups [Combinatorics, Probability and Computing, 17(3):363--387, 2008].

The earlier version had a fatal error in the proof of the soundness theorem (Claim 4.7 and Claim 4.8) that invalidated the main result. In this version, we fix the issue by working with the layered Label Cover instance. In this revised version, we have also corrected minor typographical errors and improved the overall presentation of the paper.

We sincerely thank the JACM reviewer for pointing out this error.

A seminal result of H\r{a}stad [J. ACM, 48(4):798–859, 2001] shows that it is NP-hard to find an assignment that satisfies $\frac{1}{|G|}+\varepsilon$ fraction of the constraints of a given $k$-LIN instance over an abelian group, even if there is an assignment that satisfies $(1-\varepsilon)$ fraction of the constraints, for any constant $\varepsilon>0$. Engebretsen et al. [Theoretical Computer Science, 312(1):17–45, 2004] later showed that the same hardness result holds for $k$-LIN instances over any finite non-abelian group.

Unlike the abelian case, where we can efficiently find a solution if the instance is satisfiable, in the non-abelian case, it is NP-complete to decide if a given system of linear equations is satisfiable or not, as shown by Russell and Goldmann [Information and Computation, 178(1):253–262, 2002].

Surprisingly, for certain non-abelian groups $G$, given a satisfiable $k$-LIN instance over $G$, one can in fact do better than just outputting a random assignment using a simple but clever algorithm. The approximation factor achieved by this algorithm varies with the underlying group. In this paper, we show that this algorithm is {\em optimal} by proving a tight hardness of approximation of satisfiable $k$-LIN instance over {\em any} non-abelian $G$, assuming $P \neq NP$.

As a corollary, we also get $3$-query probabilistically checkable proofs with perfect completeness over large alphabets with improved soundness.