Agreement Tests on Graphs and Hypergraphs
Authors:
- 5 March 2025
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 54 (2) , 279-320
Abstract
Agreement tests are a generalization of low degree tests that capture a local-to-global phenomenon, which forms the combinatorial backbone of most probabilistically checkable proof (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, analogously 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 standard uniform distribution [Formula: see text] to the [Formula: see text]-biased distribution [Formula: see text]. As a simple demonstration of this paradigm, we show how the low degree testing result of Alon et al. [ IEEE Trans. Inform. Theory, 51 (2005), pp. 4032–4039,] and Bhattacharyya et al. [ Proc. 51 st FOCS, IEEE, 2010, pp. 488–497], originally proved for [Formula: see text], can be extended to the [Formula: see text]-biased hypercube [Formula: see text], even for very small subconstant [Formula: see text].Keywords
All Related Versions
Funding Information
- ERC-CoG (772839)
- UGC-ISF
- Swarnajayanti
- Department of Atomic Energy, Government of India (12-R&D-TFR-5.01-0500, RTI4001)
- Israel Science Foundation (2073/21)
- Israel Science Foundation (1337/16)
This publication has 23 references indexed in Scilit:
- Direct Sum TestingSIAM Journal on Computing, 2017
- New Direct-Product Testers and 2-Query PCPsSIAM Journal on Computing, 2012
- Testing Reed–Muller CodesIEEE Transactions on Information Theory, 2005
- A Combinatorial Consistency Lemma with Application to Proving the PCP TheoremSIAM Journal on Computing, 2000
- A Parallel Repetition TheoremSIAM Journal on Computing, 1998
- Proof verification and the hardness of approximation problemsJournal of the ACM, 1998
- Probabilistic checking of proofsJournal of the ACM, 1998
- Linearity testing in characteristic twoIEEE Transactions on Information Theory, 1996
- Robust Characterizations of Polynomials with Applications to Program TestingSIAM Journal on Computing, 1996
- Self-testing/correcting with applications to numerical problemsJournal of Computer and System Sciences, 1993