Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups

A seminal result of Håstad [19] shows that for k ≥ 3, 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 − ε) fraction of the constraints, for any constant ε > 0. Engebretsen, Holmerin, and Russell [14] 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 [16]. 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 optimal by proving a tight hardness of approximation of a satisfiable k -LIN instance over any non-abelian G , assuming P ≠ 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 quasi-randomness for non-abelian groups [17].

Authors

Institutions

Publication Details

Journal
Journal of the ACM
Published
2026-11-16
DOI
https://doi.org/10.1145/3862898
Primary Topic
Complexity and Algorithms in Graphs
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups

Amey Bhangale, Subhash Khot
1 links
Journal of the ACM
Complexity and Algorithms in Graphs
article

Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups

Amey Bhangale, Subhash Khot
article en

Abstract

A seminal result of Håstad [19] shows that for k ≥ 3, 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 − ε) fraction of the constraints, for any constant ε > 0. Engebretsen, Holmerin, and Russell [14] 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 [16]. 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 optimal by proving a tight hardness of approximation of a satisfiable k -LIN instance over any non-abelian G , assuming P ≠ 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 quasi-randomness for non-abelian groups [17].

Journal of the ACM
University of California, Riverside (US), Courant Institute of Mathematical Sciences (US), New York University (US)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon