Testing odd direct sums using high dimensional expanders. (English) Zbl 1522.68741
Achlioptas, Dimitris (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques, 22nd international conference, APPROX 2019, and 23rd international conference, RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20–22, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 145, Article 50, 20 p. (2019).
Summary: 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 by T. Kaufman and A. Lubotzky [ITCS 2014, 501–506 (2014; Zbl 1365.68462)] 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.
For the entire collection see [Zbl 1423.68013].
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.
For the entire collection see [Zbl 1423.68013].
MSC:
| 68W20 | Randomized algorithms |
| 05C48 | Expander graphs |
| 05E45 | Combinatorial aspects of simplicial complexes |
Citations:
Zbl 1365.68462References:
| [1] | 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. · Zbl 0867.68060 |
| [2] | 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. · Zbl 1192.94089 |
| [3] | 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. · Zbl 0795.68131 |
| [4] | Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar. Direct sum testing. SIAM Journal on Computing, 46(4):1336-1369, 2017. · Zbl 1371.68322 |
| [5] | Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM (JACM), 54(3):12, 2007. · Zbl 1292.68074 |
| [6] | Irit Dinur and Tali Kaufman. High dimensional expanders imply agreement expanders. Electronic Colloquium on Computational Complexity (ECCC), 2017. |
| [7] | 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. · Zbl 1376.05095 |
| [8] | 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. · Zbl 1082.68123 |
| [9] | 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. · Zbl 1365.68462 |
| [10] | Tali Kaufman and David Mass. High Dimensional Combinatorial Random Walks and Colorful Expansion. In ITCS, 2017. · Zbl 1402.05197 |
| [11] | Alexander Lubotzky, Beth Samuels, and Uzi Vishne. Ramanujan complexes of typeà d . Israel Journal of Mathematics, 149(1):267-299, 2005. · Zbl 1087.05036 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
