Optimal inapproximability of satisfiable k-LIN over non-abelian groups

Amey Bhangale, Subhash Khot

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A seminal result of Håstad (2001) shows that it is NP-hard to find an assignment that satisfies 1/|G|+? 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 (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 (1999). 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 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 the quasi-random properties of the non-abelian groups defined by Gowers (2008).

Original languageEnglish (US)
Title of host publicationSTOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
EditorsSamir Khuller, Virginia Vassilevska Williams
PublisherAssociation for Computing Machinery
Number of pages14
ISBN (Electronic)9781450380539
StatePublished - Jun 15 2021
Event53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, Italy
Duration: Jun 21 2021Jun 25 2021

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Conference53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
CityVirtual, Online


  • constraint satisfaction problems
  • hardness of approximation
  • linear equations
  • non-abelian groups

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Optimal inapproximability of satisfiable k-LIN over non-abelian groups'. Together they form a unique fingerprint.

Cite this