TY - GEN

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

AU - Bhangale, Amey

AU - Khot, Subhash

N1 - Funding Information:
∗Research funded by NSF grant CCF-1813438, Simons Investigator Award, and Simons Collaboration on Algorithms and Geometry.
Publisher Copyright:
© 2021 ACM.

PY - 2021/6/15

Y1 - 2021/6/15

N2 - 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).

AB - 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).

KW - constraint satisfaction problems

KW - hardness of approximation

KW - linear equations

KW - non-abelian groups

UR - http://www.scopus.com/inward/record.url?scp=85108178222&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85108178222&partnerID=8YFLogxK

U2 - 10.1145/3406325.3451003

DO - 10.1145/3406325.3451003

M3 - Conference contribution

AN - SCOPUS:85108178222

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1615

EP - 1628

BT - STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

A2 - Khuller, Samir

A2 - Williams, Virginia Vassilevska

PB - Association for Computing Machinery

T2 - 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021

Y2 - 21 June 2021 through 25 June 2021

ER -