LIPIcs.APPROX-RANDOM.2022.5.pdf
- Filesize: 0.61 MB
- 10 pages
Document
High Dimensional Expansion Implies Amplified Local Testability
Authors
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
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 4.0 International license
- Publication Date: 2022-09-15
File
Document Identifiers
Cite AsGet BibTex
Tali Kaufman and Izhar Oppenheim. High Dimensional Expansion Implies Amplified Local Testability. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 5:1-5:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.5
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.5
Abstract
In this work, we define a notion of local testability of codes that is strictly stronger than the basic one (studied e.g., by recent works on high rate LTCs), and we term it amplified local testability. Amplified local testability is a notion close to the result of optimal testing for Reed-Muller codes achieved by Bhattacharyya et al.
We present a scheme to get amplified locally testable codes from high dimensional expanders. We show that single orbit Affine invariant codes, and in particular Reed-Muller codes, can be described via our scheme, and hence are amplified locally testable. This gives the strongest currently known testability result of single orbit affine invariant codes, strengthening the celebrated result of Kaufman and Sudan.
Subject Classification
ACM Subject Classification
- Theory of computation → Expander graphs and randomness extractors
- Theory of computation → Error-correcting codes
Keywords
- Locally testable codes
- High dimensional expanders
- Amplified testing
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing Reed-Muller codes. IEEE Trans. Inform. Theory, 51(11):4032-4039, 2005. URL: https://doi.org/10.1109/TIT.2005.856958.
-
Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. Optimal testing of Reed-Muller codes. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science - FOCS 2010, pages 488-497. IEEE Computer Soc., Los Alamitos, CA, 2010.
- Yotam Dikstein, Irit Dinur, Prahladh Harsha, and Noga Ron-Zewi. Locally testable codes via high-dimensional expanders, 2020. URL: http://arxiv.org/abs/2005.01045.
- Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes. Locally testable codes with constant rate, distance, and locality, 2021. URL: http://arxiv.org/abs/2111.04808.
- Shai Evra and Tali Kaufman. Bounded degree cosystolic expanders of every dimension. In STOC'16 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 36-48. ACM, New York, 2016. URL: https://doi.org/10.1145/2897518.2897543.
- Elad Haramaty, Noga Ron-Zewi, and Madhu Sudan. Absolutely sound testing of lifted codes. Theory Comput., 11:299-338, 2015. URL: https://doi.org/10.4086/toc.2015.v011a012.
- Tali Kaufman, David Kazhdan, and Alexander Lubotzky. Ramanujan complexes and bounded degree topological expanders. In 55th Annual IEEE Symposium on Foundations of Computer Science - FOCS 2014, pages 484-493. IEEE Computer Soc., Los Alamitos, CA, 2014. URL: https://doi.org/10.1109/FOCS.2014.58.
- Tali Kaufman and David Mass. Cosystolic expanders over any abelian group. Electronic Colloquium on Computational Complexity (ECCC), 25:134, 2018. URL: https://eccc.weizmann.ac.il/report/2018/134.
-
Tali Kaufman and Izhar Oppenheim. High order random walks: beyond spectral gap. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques, volume 116 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 47, 17. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018.
- Tali Kaufman and Madhu Sudan. Algebraic property testing: the role of invariance. In STOC'08, pages 403-412. ACM, New York, 2008. URL: https://doi.org/10.1145/1374376.1374434.