Tata Institute of Fundamental Research
Agreement Tests on Graphs and Hypergraphs
STCS Seminar
Speaker:
Prahladh Harsha
Organiser:
Piyush Srivastava
Date:
Thursday, 30 Nov 2017, 11:30 to 12:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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 talk, we will discuss a new agreement theorem which extends direct product tests to higher dimensions, analogous to how low degree tests extend linearity testing. An immediate corollary of this agreement theorem we obtain the following: 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.
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 (joint work with Irit Dinur and Yuval Filmus).
| Speaker: | Prahladh Harsha |
| Organiser: | Piyush Srivastava |
| Date: | Thursday, 30 Nov 2017, 11:30 to 12:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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 talk, we will discuss a new agreement theorem which extends direct product tests to higher dimensions, analogous to how low degree tests extend linearity testing. An immediate corollary of this agreement theorem we obtain the following: 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.
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 (joint work with Irit Dinur and Yuval Filmus).
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 talk, we will discuss a new agreement theorem which extends direct product tests to higher dimensions, analogous to how low degree tests extend linearity testing. An immediate corollary of this agreement theorem we obtain the following: 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.
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 (joint work with Irit Dinur and Yuval Filmus).