2023/08/18 by Dikstein, Yotam, Dinur, Irit
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2308.09582
Given a family X of subsets of [n] and an ensemble of local functions \fs:s→Σ | s∈ X\, an agreement test is a randomized property tester that is supposed to test whether there is some global function G:[n]→Σ such that fs=G|s for many sets s. A "classical" small-soundness agreement theorem is a list-decoding (LD) statement, saying that Agree(\fs\) gt; ε \Longrightarrow ∃ G1,…, G^ℓ, Ps[fs\overset0.99≈Gi|s]≥ poly(ε), i=1,…,ℓ. Such a statement is motivated by PCP questions and has been shown in the case where X=\binom[n]k, or where X is a collection of low dimensional subspaces of a vector space. In this work we study small the case of on high dimensional expanders X. It has been an open challenge to analyze their small soundness behavior. Surprisingly, the small soundness behavior turns out to be governed by the topological covers of X.We show that: 1. If X has no connected covers, then (LD) holds, provided that X satisfies an additional expansion property. 2. If X has a connected cover, then (LD) necessarily fails. 3. If X has a connected cover (and assuming the additional expansion property), we replace the (LD) by a weaker statement we call lift-decoding: Agree(\fs\)gt; ε \Longrightarrow ∃ cover ρ:Y\twoheadrightarrow X, and G:Y(0)→Σ, such that P s\twoheadrightarrow s[fs \overset0.99≈ G| s] ≥ poly(ε), where s\twoheadrightarrow s means that ρ( s)=s. The additional expansion property is cosystolic expansion of a complex derived from X holds for the spherical building and for quotients of the Bruhat-Tits building.