Yotam Dikstein, Weizmann Institute of Science

Abstract

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: sin 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 probability 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 the 99%-regime, Dinur and Kaufman showed existence agreement tests where $|S|=O(|V|)$ using high dimensional expanders, and conjectured that the same is true for the 1%-regime. Later on however, it was shown that some high dimensional expanders are not sound agreement tests in the 1% regime.

In this work we overcome the barrier, and 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.

See: https://sites.google.com/view/rutgersdmseminar