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.
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.