Revision #1 Authors: Irit Dinur, Yuval Filmus, Prahladh Harsha

Accepted on: 15th December 2020 17:53

Downloads: 67

Keywords:

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,

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

We prove the agreement theorem by (re)proving the agreement theorem for dimension 1, and then

generalizing it to higher dimensions (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 the reverse union bound,

which allows us to treat dependent events as if they are disjoint, and may be of independent interest.

An added benefit of the reverse union bound is that it can be used to show that the “majority decoded”

function also serves as a global function that explains the local consistency of the agreement theorem,

a fact that was not known even in the direct product setting (dimension 1) prior to our work.

Beyond the motivation to understand fundamental local-to-global structures, our main theorem

allows us to lift structure theorems from the uniform hypercube to the p-biased hypercube. As a simple demonstration of this paradigm,

we show how the low degree testing result of of Alon et al. [IEEE Trans. Inform. Theory, 2005] and

Bhattacharyya et al. [Proc. 51st FOCS, 2010], originally proved for the uniform setting, can be extended to the p-biased

hypercube, even for very small sub-constant p.

TR17-181 Authors: Irit Dinur, Yuval Filmus, Prahladh Harsha

Publication: 26th November 2017 20:51

Downloads: 825

Keywords:

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.