LIPIcs.APPROX-RANDOM.2019.50.pdf
- Filesize: 0.52 MB
- 20 pages
Document
Testing Odd Direct Sums Using High Dimensional Expanders
Authors
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-09-17
File
Document Identifiers
Cite As Get BibTex
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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.50
Abstract
In this work, using methods from high dimensional expansion, we show that the property of k-direct-sum is testable for odd values of k . Previous work of [Kaufman and Lubotzky, 2014] could inherently deal only with the case that k is even, using a reduction to linearity testing. Interestingly, our work is the first to combine the topological notion of high dimensional expansion (called co-systolic expansion) with the combinatorial/spectral notion of high dimensional expansion (called colorful expansion) to obtain the result. The classical k-direct-sum problem applies to the complete complex; Namely it considers a function defined over all k-subsets of some n sized universe. Our result here applies to any collection of k-subsets of an n-universe, assuming this collection of subsets forms a high dimensional expander.
Subject Classification
ACM Subject Classification
- Theory of computation → Randomness, geometry and discrete structures
Keywords
- High Dimensional Expanders
- Property Testing
- Direct Sum
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Mihir Bellare, Don Coppersmith, JOHAN Hastad, Marcos Kiwi, and Madhu Sudan. Linearity testing in characteristic two. IEEE Transactions on Information Theory, 42(6):1781-1795, 1996.
-
Eli Ben-Sasson, Madhu Sudan, Salil Vadhan, and Avi Wigderson. Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 612-621. ACM, 2003.
-
Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of computer and system sciences, 47(3):549-595, 1993.
-
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar. Direct sum testing. SIAM Journal on Computing, 46(4):1336-1369, 2017.
-
Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM (JACM), 54(3):12, 2007.
-
Irit Dinur and Tali Kaufman. High dimensional expanders imply agreement expanders. Electronic Colloquium on Computational Complexity (ECCC), 2017.
-
Shai Evra and Tali Kaufman. Bounded degree cosystolic expanders of every dimension. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 36-48. ACM, 2016.
-
Eldar Fischer. The art of uninformed decisions: A primer to property testing. In Current Trends in Theoretical Computer Science: The Challenge of the New Century Vol 1: Algorithms and Complexity Vol 2: Formal Models and Semantics, pages 229-263. World Scientific, 2004.
-
Tali Kaufman and Alexander Lubotzky. High dimensional expanders and property testing. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 501-506. ACM, 2014.
-
Tali Kaufman and David Mass. High Dimensional Combinatorial Random Walks and Colorful Expansion. In ITCS, 2017.
-
Alexander Lubotzky, Beth Samuels, and Uzi Vishne. Ramanujan complexes of typeÃ_d. Israel Journal of Mathematics, 149(1):267-299, 2005.