Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NON-ABELIAN:
Reports tagged with Non-abelian:
TR20-130 | 30th August 2020
Amey Bhangale, Subhash Khot

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

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

ISSN 1433-8092 | Imprint