Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs

We solve the derandomized direct product testing question in the low acceptance regime, by constructing new high dimensional expanders that have no small connected covers. We show that our complexes have swap cocycle expansion, which allows us to deduce the agreement theorem by relying on previous work. Derandomized direct product testing, also known as agreement testing, is the following problem. Let <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X$</tex> be a family of k-element subsets of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$[N]$</tex> and let <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\{f_{s}:s\rightarrow\Sigma\vert s\in X\}$</tex> be an ensemble of local functions, each defined over a subset <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$s\subset\lceil N$</tex>. Suppose that we run the following so-called agreement test: choose a random pair of sets <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$s_{1}, s_{2}\in X$</tex> that intersect on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\sqrt{k}$</tex> elements, and accept if <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f_{s_{1}}, f_{s_{2}}$</tex> agree on the elements in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$s_{1}\cap s_{2}$</tex>. We denote the success probability of this test by Agree <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\{f_{s}\})$</tex> Given that Agree <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(\{f_{s}\})=\varepsilon &gt; 0$</tex> is there a global function <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$G:[N]\rightarrow\Sigma$</tex> such that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f_{s}=G\vert _{s}$</tex> for a non-negligible fraction of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$s\in X\ ?$</tex> We construct a family <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X$</tex> of k-subsets of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$[N]$</tex> such that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\vert X\vert =O(N)$</tex>, and such that it satisfies the low acceptance agreement theorem. Namely, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\text{Agree}\left(\left\{f_s\right\}\right)&gt;\varepsilon \Longrightarrow \exists G:[N] \rightarrow \Sigma, \quad \underset{s}{\mathbb{P}}\left[\left.f_s \stackrel{0.99}{\approx} G\right\vert_s\right] \geqslant \text{poly}(\varepsilon)$</tex>. A key idea is to replace the well-studied LSV complexes by symplectic high dimensional expanders (HDXs). The family <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$X$</tex> is just the k-faces of the new symplectic HDXs. The latter serve our needs better since their fundamental group satisfies the congruence subgroup property, which implies that they lack small covers. We also give a polynomial-time algorithm to construct this family of sym-plectic HDXs.