Computer Science/Discrete Mathematics Seminar II

Agreement testing (aka direct product testing), checks if consistent local information reveals global structure. Beyond its theoretical connections to probabilistic checkable proofs (PCPs), constructing agreement testers is a fundamental combinatorial question that has exciting applications in coding theory and hardness amplification.

Let (V,S) be a hypergraph with vertices. The direct product encoding encodes a function $g:V \to \{0,1\}$ by its restrictions $F(g)=\{g|_s: s\in S\}$. Agreement testing asks the inverse question: Given $F=\{f_s:s \to \{0,1\}: s \in S\}$, can we test whether $F$ is non-trivially close to an encoding of some $g:V \to \{0,1\}$, by querying only two random functions? The test we consider samples two random $s,s' \in S$ and accepts if $f_s = f_{s'}$ on the shared intersection. In this talk we focus on the more challenging 1%-regime, where the probability that $F$ passes the test is non-negligible, but small (1%). Hypergraphs where passing the test with non-negligible probabiliy implies correlation with some $F(g)$, are called sound agreement tests.

Constructing sound agreement tests was studied in the 90', and works in complexity inspired the goal of constructing agreement tests where the size of $S$ grows as slowly as possible with respect to $V$. Such sparse tests are an important prerequisite for derandomizing some fundamental PCP constructions.

In this work we construct novel agreement tests for the 1%-regime, where $|S|=O(|V|)$. Quite surprisingly, constructing such tests requires the hypergraph to have no small connected topological covers, along with other more combinatorial properties. We construct such hypergraphs using subgroups of the symplectic group over the piadic numbers, along with a variety of other topological and combinatorial tools from high dimensional expander theory.

This talk is based on joint work with Irit Dinur and Alex Lubotzky.