2024/11/22 by Bhangale, Amey, Khot, Subhash, Liu, Yang P. +1 · 1 citation
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2411.15136
Let Σ1,…,Σk be finite alphabets, and let μ be a distribution over Σ1 × … × Σk in which the probability of each atom is at least α. We prove that if μ does not admit Abelian embeddings, and fi: Σi → ℂ are 1-bounded functions (for i=1,…,k) such that |𝔼(x1,…,xk) ∼ μ⊗ n[f1(x1) … fk(xk)]| ≥ ε, then there exists L\colon Σ1n→ℂ of degree at most d and ‖L‖2≤ 1 such that |⟨ f1, L⟩|≥ δ, where d and δ>0 depend only on k, α and ε. This answers the analytic question posed by Bhangale, Khot, and Minzer (STOC 2022). We also prove several extensions of this result that are useful in subsequent applications.