Relaxed Locally Correctable Codes with Improved Parameters

Authors Vahid R. Asadi, Igor Shinkar



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.18.pdf
  • Filesize: 0.6 MB
  • 12 pages

Document Identifiers

Author Details

Vahid R. Asadi
  • Simon Fraser University, Burnaby, Canada
Igor Shinkar
  • Simon Fraser University, Burnaby, Canada

Acknowledgements

We are thankful to Tom Gur for many fruitful discussions on this topic, and we are grateful to the anonymous referees for their valuable suggestions that helped improve the presentation of the paper.

Cite AsGet BibTex

Vahid R. Asadi and Igor Shinkar. Relaxed Locally Correctable Codes with Improved Parameters. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 18:1-18:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.18

Abstract

Locally decodable codes (LDCs) are error-correcting codes C: Σ^k → Σⁿ that admit a local decoding algorithm that recovers each individual bit of the message by querying only a few bits from a noisy codeword. An important question in this line of research is to understand the optimal trade-off between the query complexity of LDCs and their block length. Despite importance of these objects, the best known constructions of constant query LDCs have super-polynomial length, and there is a significant gap between the best constructions and the known lower bounds in terms of the block length. For many applications it suffices to consider the weaker notion of relaxed LDCs (RLDCs), which allows the local decoding algorithm to abort if by querying a few bits it detects that the input is not a codeword. This relaxation turned out to allow decoding algorithms with constant query complexity for codes with almost linear length. Specifically, [{Ben-Sasson} et al., 2006] constructed a q-query RLDC that encodes a message of length k using a codeword of block length n = O_q(k^{1+O(1/√q)}) for any sufficiently large q, where O_q(⋅) hides some constant that depends only on q. In this work we improve the parameters of [{Ben-Sasson} et al., 2006] by constructing a q-query RLDC that encodes a message of length k using a codeword of block length O_q(k^{1+O(1/{q})}) for any sufficiently large q. This construction matches (up to a multiplicative constant factor) the lower bounds of [Jonathan Katz and Trevisan, 2000; Woodruff, 2007] for constant query LDCs, thus making progress toward understanding the gap between LDCs and RLDCs in the constant query regime. In fact, our construction extends to the stronger notion of relaxed locally correctable codes (RLCCs), introduced in [Tom Gur et al., 2018], where given a noisy codeword the correcting algorithm either recovers each individual bit of the codeword by only reading a small part of the input, or aborts if the input is detected to be corrupt.

Subject Classification

ACM Subject Classification
  • Theory of computation → Error-correcting codes
Keywords
  • Algorithmic coding theory
  • consistency test using random walk
  • Reed-Muller code
  • relaxed locally decodable codes
  • relaxed locally correctable codes

Metrics

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

References

  1. Vahid R. Asadi and Igor Shinkar. Relaxed locally correctable codes with improved parameters. Electron. Colloquium Comput. Complex., 2020. URL: https://eccc.weizmann.ac.il/report/2020/142.
  2. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM Journal on Computing, 36(4):889-974, 2006. Google Scholar
  3. Alessandro Chiesa, Tom Gur, and Igor Shinkar. Relaxed locally correctable codes with nearly-linear block length and constant query complexity. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1395-1411, 2020. Google Scholar
  4. A. Deshpande, R. Jain, T. Kavitha, S. V. Lokam, and J. Radhakrishnan. Better lower bounds for locally decodable codes. In Proceedings 17th IEEE Annual Conference on Computational Complexity, pages 184-193, 2002. Google Scholar
  5. Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha. Boolean Function Analysis on High-Dimensional Expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1-38:20, 2018. Google Scholar
  6. I. Dinur and T. Kaufman. High dimensional expanders imply agreement expanders. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 974-985, 2017. Google Scholar
  7. Irit Dinur, Oded Goldreich, and Tom Gur. Every set in P is strongly testable under a suitable encoding. Electron. Colloquium Comput. Complex., 2018. URL: https://eccc.weizmann.ac.il/report/2018/050.
  8. Irit Dinur and Omer Reingold. Assignment testers: Towards a combinatorial proof of the PCP theorem. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004, pages 155-164, 2004. Google Scholar
  9. Klim Efremenko. 3-query locally decodable codes of subexponential length. SIAM J. Comput., 41(6):1694-1703, 2012. Google Scholar
  10. O. Goldreich, H. Karloff, L. J. Schulman, and L. Trevisan. Lower bounds for linear locally decodable codes and private information retrieval. In Proceedings 17th IEEE Annual Conference on Computational Complexity, pages 175-183, 2002. Google Scholar
  11. Oded Goldreich and Madhu Sudan. Locally testable codes and pcps of almost-linear length. J. ACM, 53(4):558-655, 2006. Google Scholar
  12. Tom Gur and Oded Lachish. A lower bound for relaxed locally decodable codes. In 31st ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, 2020. Google Scholar
  13. Tom Gur, Govind Ramnarayan, and Ron D. Rothblum. Relaxed locally correctable codes. In 9th Innovations in Theoretical Computer Science Conference, ITCS '18, pages 27:1-27:11, 2018. Google Scholar
  14. 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
  15. Tali Kaufman and David Mass. High Dimensional Random Walks and Colorful Expansion. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1-4:27, 2017. Google Scholar
  16. Tali Kaufman and Izhar Oppenheim. High Order Random Walks: Beyond Spectral Gap. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), Leibniz International Proceedings in Informatics (LIPIcs), pages 47:1-47:17, 2018. Google Scholar
  17. Iordanis Kerenidis and Ronald de Wolf. Exponential lower bound for 2-query locally decodable codes via a quantum argument. In Journal of Computer and System Sciences, pages 106-115, 2003. Google Scholar
  18. Swastik Kopparty and Shubhangi Saraf. Local testing and decoding of high-rate error-correcting codes. Electron. Colloquium Comput. Complex., 2017. URL: https://eccc.weizmann.ac.il/report/2017/126.
  19. Kenji Obata. Optimal lower bounds for 2-query locally decodable linear codes. In Randomization and Approximation Techniques in Computer Science, pages 39-50, 2002. Google Scholar
  20. Orr Paradise. Smooth and strong pcps. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, 2020. Google Scholar
  21. Noga Ron-Zewi and Ron Rothblum. Local proofs approaching the witness length. Electron. Colloquium Comput. Complex., 2019. URL: https://eccc.weizmann.ac.il/report/2019/127.
  22. Stephanie Wehner and Ronald de Wolf. Improved lower bounds for locally decodable codes and private information retrieval. In Proceedings of the 32nd International Conference on Automata, Languages and Programming, ICALP'05, pages 1424–-1436, 2005. Google Scholar
  23. David Woodruff. New lower bounds for general locally decodable codes. Electron. Colloquium Comput. Complex., 2007. URL: https://eccc.weizmann.ac.il/report/2007/006/.
  24. David P. Woodruff. A quadratic lower bound for three-query linear locally decodable codes over any field. In Proceedings of the 14th International Workshop on Randomized Techniques in Computation, RANDOM 10, pages 766-779, 2010. Google Scholar
  25. Sergey Yekhanin. Towards 3-query locally decodable codes of subexponential length. J. ACM, 55(1):1:1-1:16, 2008. Google Scholar
  26. Sergey Yekhanin. Locally decodable codes. Foundations and Trends in Theoretical Computer Science, 6(3):139-255, 2012. 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