2026-08-08T16:10:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17127 2024-03-06T10:59:02Z ddc:004 open_access

High Dimensional Expansion Implies Amplified Local Testability Kaufman, Tali Oppenheim, Izhar Locally testable codes High dimensional expanders Amplified testing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tali Kaufman and Izhar Oppenheim 2022 Is Part Of LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2022.5 urn:nbn:de:0030-drops-171276 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.5 eng https://creativecommons.org/licenses/by/4.0/legalcode