## New Derandomized Agreement Tests

by Yotam Dikstein, Irit Dinur, and Alex Lubotzky.

#### Oded's comments

Yotam started with a commendable introduction to this research direction
at large.
The context consists of a set of "points" P,
a set of $k$-subsets $S\subseteq{P\choose k}$, for a relatively small k,
and a distribution $D$ over pairs of subsets.
The "full" case corresponds to $S = {P\choose k}$,
whereas extremely sparse case corresponds to $|S| = O|P|)$.

We are given oracle access to a set of (local) function $f_s:s\to\Sigma$,
for every $s\in S$,
and the question is whether there exists a (global) function $g:P\to\Sigma$
such that $g|_s = f_s$ for every $s\in S$.
Actually, we are interested in $(\rho,\eps)$-soundness that asserts that
if the probability that a pair of sets (drawn according to D) are in agreement
(i.e.,, $f_{s_1}(e) = f_{s_2}(e)$ for every $e \in s_1 \cap s_2$)
is at least $\rho$,
then at least $\eps$ of the locals functions are in agreement
with some global function $g$
(where agreement on $s\in S$ may mean either $g|_s = f_s$
or that equality holds for almost all elements of $s$).
This relation between rho and eps is typically consider are two regimes.

- The "high agreement" regime
(e.g., $\rho = 0.99$ and $\eps = 0.9$)
corresponds to the standard in property testing (and LTCs).
It refers to low probability of error, and the prior work of
Dinur and Kaufman (2017) refers to it,
and uses $|S| = O(|P|)$ and constant $k$.
- The "low agreement" regime
(e.g., $\rho = 0.01$ and $\eps = 0.001$)
is used in advanced PCP constructions. .
(In these case the agreement of $g$ with the $f_s$'s
is relaxed as mentioned above.)
The current work is in this regime
and (also) uses $|S| = O(|P|)$ and constant $k$.

#### The original 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.

In recent work we construct new derandomized `1%-regime' agreement tests. Derandomization of these tests is an important stepping stone towards derandomizing many PCPs, such as the parallel repetition PCP.

We will define agreement tests and give some background on their importance. Then we will see a surprising connection between agreement testing to a problem in algebraic topology. Finally, we will discuss how strong group theoretic tools solve this problem and lead to our construction.

Back to
list of Oded's choices.