2024/02/01 by Mitali Bafna, Bafna, Mitali, Noam Lifshitz +3
Engineering · #Advanced Measurement and Metrology Techniques #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Industrial Vision Systems and Defect Detection
paper · pdf · doi:10.48550/arxiv.2402.00850
openalex publication_date 2024/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let X be a d-dimensional simplicial complex. A function F\colon X(k)→ \0,1\k is said to be a direct product function if there exists a function f\colon X(1)→ \0,1\ such that F(σ) = (f(σ1), …, f(σk)) for each k-face σ. In an effort to simplify components of the PCP theorem, Goldreich and Safra introduced the problem of direct product testing, which asks whether one can test if F\colon X(k)→ \0,1\k is correlated with a direct product function by querying F on only 2 inputs. Dinur and Kaufman conjectured that there exist bounded degree complexes with a direct product test in the small soundness regime. We resolve their conjecture by showing that for all δ>0, there exists a family of high-dimensional expanders with degree Oδ(1) and a 2-query direct product tester with soundness δ. We use the characterization given by a subset of the authors and independently by Dikstein and Dinur, who showed that some form of non-Abelian coboundary expansion (which they called "Unique-Games coboundary expansion") is a necessary and sufficient condition for a complex to admit such direct product testers. Our main technical contribution is a general technique for showing coboundary expansion of complexes with coefficients in a non-Abelian group. This allows us to prove that the high dimensional expanders constructed by Chapman and Lubotzky satisfies the necessary conditions, thus admitting a 2-query direct product tester with small soundness.