Document Open Access Logo

List Agreement Expansion from Coboundary Expansion

Authors Roy Gotlib, Tali Kaufman

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.61.pdf
  • Filesize: 0.75 MB
  • 23 pages

Document Identifiers

Author Details

Roy Gotlib
  • Department of Computer Science, Bar-Ilan University, Ramat-Gan, Israel
Tali Kaufman
  • Department of Computer Science, Bar-Ilan University, Ramat-Gan, Israel

Funding

  • Gotlib, Roy: Research supported by ERC.
  • Kaufman, Tali: Research supported by ERC and BSF.

Cite As Get BibTex

Roy Gotlib and Tali Kaufman. List Agreement Expansion from Coboundary Expansion. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 61:1-61:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.61

Abstract

One of the key components in PCP constructions are agreement tests. In agreement test the tester is given access to subsets of fixed size of some set, each equipped with an assignment. The tester is then tasked with testing whether these local assignments agree with some global assignment over the entire set. One natural generalization of this concept is the case where, instead of a single assignment to each local view, the tester is given access to l different assignments for every subset. The tester is then tasked with testing whether there exist l global functions that agree with all of the assignments of all of the local views. In this work we present sufficient condition for a set system to exhibit this generalized definition of list agreement expansion. This is, to our knowledge, the first work to consider this natural generalization of agreement testing.
Despite initially appearing very similar to agreement expansion in definition, proving that a set system exhibits list agreement expansion seem to require a different set of techniques. This is due to the fact that the natural extension of agreement testing (i.e. that there exists a pairing of the lists such that each pair agrees with each other) does not suffice when testing for list agreement as list agreement crucially relies on a global structure. It follows that if a local assignments satisfy list agreement they must not only agree locally but also exhibit some additional structure. In order to test for the existence of this additional structure we use the connection between covering spaces of a high dimensional complex and its coboundaries. Specifically, we use this connection as a form of "decoupling".
Moreover, we show that any set system that exhibits list agreement expansion also supports direct sum testing. This is the first scheme for direct sum testing that works regardless of the parity of the sizes of the local sets. Prior to our work the schemes for direct sum testing were based on the parity of the sizes of the local tests.

Subject Classification

ACM Subject Classification
  • Theory of computation → Randomness, geometry and discrete structures
Keywords
  • High dimensional Expanders
  • Property Testing
  • Agreement Testing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Boaz Barak, Pravesh K Kothari, and David Steurer. Small-set expansion in shortcode graph and the 2-to-2 conjecture. arXiv preprint, 2018. URL: http://arxiv.org/abs/1804.08662.
  2. Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar. Direct sum testing. SIAM Journal on Computing, 46(4):1336-1369, 2017. Google Scholar
  3. Yotam Dikstein and Irit Dinur. Agreement testing theorems on layered set systems. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1495-1524. IEEE, 2019. Google Scholar
  4. Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha. Boolean functions on high-dimensional expanders. arXiv preprint, 2018. URL: http://arxiv.org/abs/1804.08155.
  5. Yotam Dikstein, Irit Dinur, Prahladh Harsha, and Noga Ron-Zewi. Locally testable codes via high-dimensional expanders. arXiv preprint, 2020. URL: http://arxiv.org/abs/2005.01045.
  6. Irit Dinur, Yuval Filmus, and Prahladh Harsha. Agreement tests on graphs and hypergraphs. arXiv preprint, 2017. URL: http://arxiv.org/abs/1711.09426.
  7. Irit Dinur, Yuval Filmus, and Prahladh Harsha. Analyzing boolean functions on the biased hypercube via higher-dimensional agreement tests. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2124-2133. SIAM, 2019. Google Scholar
  8. Irit Dinur, Prahladh Harsha, Tali Kaufman, and Noga Ron-Zewi. From local to robust testing via agreement testing. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  9. Irit Dinur and Tali Kaufman. High dimensional expanders imply agreement expanders. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 974-985. IEEE, 2017. Google Scholar
  10. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Towards a proof of the 2-to-1 games conjecture? In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 376-389, 2018. Google Scholar
  11. Irit Dinur and Roy Meshulam. Near coverings and cosystolic expansion-an example of topological property testing. arXiv preprint, 2019. URL: http://arxiv.org/abs/1909.08507.
  12. Roy Gotlib and Tali Kaufman. Testing odd direct sums using high dimensional expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  13. Roy Gotlib and Tali Kaufman. List agreement expansion from coboundary expansion, 2022. URL: https://doi.org/10.48550/arXiv.2210.15714.
  14. Mikhail Gromov. Singularities, expanders and topology of maps. part 2: From combinatorics to topology via algebraic isoperimetry. Geometric and Functional Analysis, 20(2):416-526, 2010. Google Scholar
  15. Russell Impagliazzo, Ragesh Jaiswal, and Valentine Kabanets. Approximate list-decoding of direct product codes and uniform hardness amplification. SIAM Journal on Computing, 39(2):564-605, 2009. Google Scholar
  16. Tali Kaufman and Alexander Lubotzky. High dimensional expanders and property testing. In Moni Naor, editor, Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pages 501-506. ACM, 2014. URL: https://doi.org/10.1145/2554797.2554842.
  17. Tali Kaufman and David Mass. Local-to-global agreement expansion via the variance method. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  18. Tali Kaufman and David Mass. Unique-neighbor-like expansion and group-independent cosystolic expansion. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  19. Subhash Khot, Dor Minzer, and Muli Safra. On independent sets, 2-to-2 games, and grassmann graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 576-589, 2017. Google Scholar
  20. Nathan Linial and Roy Meshulam. Homological connectivity of random 2-complexes. Combinatorica, 26(4):475-487, 2006. Google Scholar
  21. David B Surowski. Covers of simplicial complexes and applications to geometry. Geometriae Dedicata, 16(1):35-62, 1984. Google Scholar
  22. Andrew C. Yao. Theory and application of trapdoor functions. In 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pages 80-91, 1982. URL: https://doi.org/10.1109/SFCS.1982.45.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact