EUVIMEDEUVIMED entdecken
Crossref

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

Amey Bhangale, Subhash Khot

Journal of the ACM · 16.11.2026

DOI: 10.1145/3862898 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 16.11.2026. Verfasst von Amey Bhangale und 1 weiteren Autor:innen. Die Arbeit nennt 24 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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].

Zitieren

APA

Bhangale, A., & Khot, S. (2026). Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups. Journal of the ACM. https://doi.org/10.1145/3862898

Vancouver

Bhangale A, Khot S. Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups. Journal of the ACM. 2026. doi:10.1145/3862898

BibTeX
@article{Bhangale2026,
  author = {Bhangale, Amey and Khot, Subhash},
  title = {Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups},
  journal = {Journal of the ACM},
  year = {2026},
  doi = {10.1145/3862898}
}
Kostenlos starten →