Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs
summary
Proves that MAX-3-LIN over any finite non-abelian group is UFG NP-hard to approximate to (1−ε, 1/|G|+ε) and gives a matching UFG hardness for satisfiable instances with soundness 1/|[G,G]|+ε, where [G,G] is the commutator subgroup. The proof uses representation theory and non-abelian Fourier analysis, a new PCP test and functional folding, and outputs cleaner constraint instances with no inter-variable constants or inverses; all reductions are constructive and yield the stated hardness parameters.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 0:23Outline
- 0:51Algorithm
- 1:37NP Hard
- 2:20Max3Lin over G
- 4:47System of equations
- 8:08Universal Factor Graphs
- 9:23Universal Factor Graph Hardness
- 11:52Universal Factor Graph Comparison
- 13:04Functional Folding
- 14:50Representation Theory
- 17:01Fourier Analysis
- 18:08Dilemma
- 20:37Results
related talks
01h 01mTrue Complexity of Multilinear Systems
01h 31mTutorial 1: The GCT Chasm I
01h 22mTutorial 3: Geometric Invariant Theory
28mWiP: Labeled Union-Find for Constraint Factorization
47mHardness Amplification and the Approximate Degree of Constant-Depth Circuits
21mRelating Distances and Abstractions: An Abstract Interpretation Perspective
01h 03mUnderstanding ReLU Networks Through Graph Problems and Polyhedra
23mVerifying Graph Algorithms in Separation Logic: A Case for an Algebraic Approach