The general context of agreement tests consists of inspecting few local views in $\{f_S:S\to\bitset\}_{S\in\C}$ of a hypothetical global function $F:U\to\bitset$, where $\C$ is a collection of subsets of the universe $U$. That is, the purported object is associated with $F$, but we don't have access to it and rather inspect local views $f_S$'s associated with various $S$'s. The agreement testing task is to infer the existence of a global object that is close to the collection of local views by checking the consistency of few local views, where the tuple of views is selected at random (i.e., typically each view is uniformly distributed in $\C$ but the inspected views are dependent or else no meaningful checking of consistency is possible).
The archetypical case (aka direct product tests)
is when no structure is postulated on $U$,
and $\C$ is the collection of all $k$-subsets of $U$.
In typical derandomized versions the collection $\C$
is a small family of $k$-subsets (e.g., a family that
is generated by an adequate pseudorandom generator).
In some cases, the definition of this pseudorandom generator imposes
a structure on $U$ (e.g., $U$ may be have the form $W\times W$
[GS00],
or $U$ may be a $d$-dimensional vector space over a finite field
[IKW12 as well as prior work
and more]),
and a corresponding restriction on $\C$
(e.g., each $S\in\C$ must have the form $R_1\times R_2$
or must be a $d'$-dimensional vector space).
The current work considers the case that $U = {V\choose2}$ is
the set of possible edges of a graph $G$ viewed as a function;
that is, the set of edges are $G^{-1}(1) \subseteq U$.
Accodingly, the local views are subgraphs induced small sets
of vertices; that is, $\C$ is the family of all sets $W\choose2$,
where $W\subset V$ is of a specified size.
Hence, given access to subgraphs that correspond
to ceratin vertex sets, the task is to determine
whether they are close to fit a single graph
(i.e., are induced subgraphs of a single graph).
This naturally generalized to hypergraphs,
viewing the archetypical case as a 1-dimensional hypergraph.
I wish to stress that, in this case, the structure on the universe $U$
is imposed by natural circumstances that refer to (hyper)graphs
rather than being introduced for the sake of derandomization.
Furthermore, the agreement framework extends naturally to testing
whether such local views fit a (hyper)graph with certain properties.
Agreement tests are a generalization of low degree tests that capture a
local-to-global phenomenon, which forms the combinatorial backbone of most
PCP constructions. In an agreement test, a function is given by an ensemble
of local restrictions. The agreement test checks that the restrictions
agree when they overlap, and the main question is whether average agreement
of the local pieces implies that there exists a global function that agrees
with most local restrictions.
There are very few structures that support agreement tests, essentially
either coming from algebraic low degree tests or from direct product tests
(and recently also from high dimensional expanders). In this work, we prove
a new agreement theorem which extends direct product tests to higher
dimensions, analogous to how low degree tests extend linearity testing. As
a corollary of our main theorem, we show that an ensemble of small graphs
on overlapping sets of vertices can be glued together to one global graph
assuming they agree with each other on average.
Our agreement theorem is proven by induction on the dimension (with the
dimension 1 case being the direct product test, and dimension 2 being the
graph case). A key technical step in our proof is a new hypergraph pruning
lemma which allows us to treat dependent events as if they are disjoint,
and may be of independent interest.
Beyond the motivation to understand fundamental local-to-global structures,
our main theorem is used in a completely new way in a recent
paper by the authors
for proving a structure theorem for Boolean functions on the
$p$-biased hypercube. The idea is to approximate restrictions of the
Boolean function on simpler sub-domains, and then use the agreement theorem
to glue them together to get a single global approximation.
See ECCC TR17-181.
The original abstract
Back to
list of Oded's choices.