Document Open Access Logo

LCC and LDC: Tailor-Made Distance Amplification and a Refined Separation

Authors Gil Cohen, Tal Yankovitz

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.44.pdf
  • Filesize: 0.76 MB
  • 20 pages

Document Identifiers

Author Details

Gil Cohen
  • Department of Computer Science, Tel Aviv University, Israel
Tal Yankovitz
  • Department of Computer Science, Tel Aviv University, Israel

Funding

The research leading to these results has received funding from the ERC starting grant 949499, the Israel Science Foundation grant 1569/18 and from the Azrieli Faculty Fellowship.

Cite AsGet BibTex

Gil Cohen and Tal Yankovitz. LCC and LDC: Tailor-Made Distance Amplification and a Refined Separation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 44:1-44:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.44

Abstract

The Alon-Edmonds-Luby distance amplification procedure (FOCS 1995) is an algorithm that transforms a code with vanishing distance to a code with constant distance. AEL was invoked by Kopparty, Meir, Ron-Zewi, and Saraf (J. ACM 2017) for obtaining their state-of-the-art LDC, LCC and LTC. Cohen and Yankovitz (CCC 2021) devised a procedure that can amplify inverse-polynomial distances, exponentially extending the regime of distances that can be amplified by AEL. However, the improved procedure only works for LDC and assuming rate 1-1/(poly log n). In this work we devise a distance amplification procedure for LCC with inverse-polynomial distances even for vanishing rate 1/(poly log log n). For LDC, we obtain a more modest improvement and require rate 1-1/(poly log log n). Thus, the tables have turned and it is now LCC that can be better amplified. Our key idea for accomplishing this, deviating from prior work, is to tailor the distance amplification procedure to the code at hand. Our second result concerns the relation between linear LDC and LCC. We prove the existence of linear LDC that are not LCC, qualitatively extending a separation by Kaufman and Viderman (RANDOM 2010).

Subject Classification

ACM Subject Classification
  • Theory of computation → Error-correcting codes
Keywords
  • Locally Correctable Codes
  • Locally Decodable Codes
  • Distance Amplifications

Metrics

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

Related Versions

References

  1. Noga Alon, Jeff Edmonds, and Michael Luby. Linear time erasure codes with nearly optimal recovery. In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 512-519. IEEE, 1995. Google Scholar
  2. Noga Alon and Michael Luby. A linear time erasure-resilient code with nearly optimal recovery. IEEE Transactions on Information Theory, 42(6):1732-1736, 1996. Google Scholar
  3. Boaz Barak, Zeev Dvir, Amir Yehudayoff, and Avi Wigderson. Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 519-528, 2011. Google Scholar
  4. Arnab Bhattacharyya, Zeev Dvir, Amir Shpilka, and Shubhangi Saraf. Tight lower bounds for 2-query lccs over finite fields. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 638-647. IEEE, 2011. Google Scholar
  5. Arnab Bhattacharyya, Sivakanth Gopi, and Avishay Tal. Lower bounds for 2-query lccs over large alphabet. arXiv preprint, 2016. URL: http://arxiv.org/abs/1611.06980.
  6. Gil Cohen and Tal Yankovitz. Lcc and ldc: Tailor-made distance amplification and a refined separation. Electronic Colloquium on Computational Complexity (ECCC), 136, 2021. Google Scholar
  7. Gil Cohen and Tal Yankovitz. Rate amplification and query-efficient distance amplification for linear lcc and ldc. In 36th Computational Complexity Conference (CCC 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  8. Irit Dinur. The PCP theorem by gap amplification. In Proc. 38th ACM Symp. on Theory of Computing, pages 241-250, 2006. Google Scholar
  9. Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin. Matching vector codes. SIAM Journal on Computing, 40(4):1154-1178, 2011. Google Scholar
  10. Zeev Dvir and Kalina Petrova. Lecture 1: Introduction. Lecture notes: https://www.cs.princeton.edu/~zdvir/LDCnotes/LDC1.pdf, 2016.
  11. Klim Efremenko. 3-query locally decodable codes of subexponential length. SIAM Journal on Computing, 41(6):1694-1703, 2012. Google Scholar
  12. Sivakanth Gopi, Swastik Kopparty, Rafael Oliveira, Noga Ron-Zewi, and Shubhangi Saraf. Locally testable and locally correctable codes approaching the gilbert-varshamov bound. IEEE Transactions on Information Theory, 64(8):5813-5831, 2018. Google Scholar
  13. Alan Guo, Swastik Kopparty, and Madhu Sudan. New affine-invariant codes from lifting. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 529-540. ACM, 2013. Google Scholar
  14. Brett Hemenway, Rafail Ostrovsky, and Mary Wootters. Local correctability of expander codes. Information and Computation, 243:178-190, 2015. Google Scholar
  15. Jonathan Katz and Luca Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 80-86, 2000. Google Scholar
  16. Tali Kaufman and Michael Viderman. Locally testable vs. locally decodable codes. In Approximation, randomization, and combinatorial optimization, volume 6302 of Lecture Notes in Comput. Sci., pages 670-682. Springer, Berlin, 2010. URL: https://doi.org/10.1007/978-3-642-15369-3_50.
  17. Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. High-rate locally correctable and locally testable codes with sub-polynomial query complexity. Journal of the ACM (JACM), 64(2):11, 2017. Google Scholar
  18. Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin. High-rate codes with sublinear-time decoding. Journal of the ACM (JACM), 61(5):28, 2014. Google Scholar
  19. A. Ta-Shma. Explicit, almost optimal, epsilon-balanced codes. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 238-251. ACM, 2017. Google Scholar
  20. Sergey Yekhanin. Towards 3-query locally decodable codes of subexponential length. Journal of the ACM (JACM), 55(1):1-16, 2008. Google Scholar
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 Imprint Privacy Contact