Document Open Access Logo

Relaxed Locally Correctable Codes

Authors Tom Gur, Govind Ramnarayan, Ron D. Rothblum

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2018.27.pdf
  • Filesize: 0.52 MB
  • 11 pages

Document Identifiers

Subject Classification

Keywords
  • Keywords and phrases Coding Theory
  • Locally Correctable Codes
  • Probabilistically Checkable Proofs

Metrics

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

Abstract

Locally decodable codes (LDCs) and locally correctable codes (LCCs) are error-correcting codes in which individual bits of the message and codeword, respectively, can be recovered by querying only few bits from a noisy codeword. These codes have found numerous applications both in theory and in practice.

A natural relaxation of LDCs, introduced by Ben-Sasson et al. (SICOMP, 2006), allows the decoder to reject (i.e., refuse to answer) in case it detects that the codeword is corrupt. They call such a decoder a relaxed decoder and construct a constant-query relaxed LDC with almost-linear blocklength, which is sub-exponentially better than what is known for (full-fledged) LDCs in the constant-query regime.

We consider an analogous relaxation for local correction. Thus, a relaxed local corrector reads only few bits from a (possibly) corrupt codeword and either recovers the desired bit of the codeword, or rejects in case it detects a corruption.

We give two constructions of relaxed LCCs in two regimes, where the first optimizes the query complexity and the second optimizes the rate:

1. Constant Query Complexity: A relaxed LCC with polynomial blocklength whose corrector only reads a constant number of bits of the codeword. This is a sub-exponential improvement over the best constant query (full-fledged) LCCs that are known.

2. Constant Rate: A relaxed LCC with constant rate (i.e., linear blocklength) with quasi-polylogarithmic query complexity. This is a nearly sub-exponential improvement over the query complexity of a recent (full-fledged) constant-rate LCC of Kopparty et al. (STOC, 2016).

Cite As Get BibTex

Tom Gur, Govind Ramnarayan, and Ron D. Rothblum. Relaxed Locally Correctable Codes. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 27:1-27:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ITCS.2018.27

Author Details

Tom Gur
Govind Ramnarayan
Ron D. Rothblum

References

  1. Noga Alon, Jeff Edmonds, and Michael Luby. Linear time erasure codes with nearly optimal recovery. In Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on, pages 512-519. IEEE, 1995. Google Scholar
  2. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM (JACM), 45(3):501-555, 1998. Google Scholar
  3. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70-122, 1998. URL: http://dx.doi.org/10.1145/273865.273901.
  4. László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Cris Koutsougeras and Jeffrey Scott Vitter, editors, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 21-31. ACM, 1991. URL: http://dx.doi.org/10.1145/103418.103428.
  5. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust pcps of proximity, shorter pcps, and applications to coding. SIAM J. Comput., 36(4):889-974, 2006. URL: http://dx.doi.org/10.1137/S0097539705446810.
  6. Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, and Arie Matsliah. Sound 3-query pcpps are long. TOCT, 1(2):7:1-7:49, 2009. URL: http://dx.doi.org/10.1145/1595391.1595394.
  7. Clément L. Canonne and Tom Gur. An adaptivity hierarchy theorem for property testing. Computational Complexity Conference (CCC), 2017. Google Scholar
  8. Irit Dinur and Prahladh Harsha. Composition of low-error 2-query pcps using decodable pcps. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 472-481. IEEE Computer Society, 2009. URL: http://dx.doi.org/10.1109/FOCS.2009.8.
  9. Irit Dinur and Omer Reingold. Assignment testers: Towards a combinatorial proof of the PCP theorem. SIAM J. Comput., 36(4):975-1024, 2006. URL: http://dx.doi.org/10.1137/S0097539705446962.
  10. Klim Efremenko. 3-query locally decodable codes of subexponential length. SIAM J. Comput., 41(6):1694-1703, 2012. URL: http://dx.doi.org/10.1137/090772721.
  11. Oded Goldreich and Tom Gur. Universal locally testable codes. Electronic Colloquium on Computational Complexity (ECCC), 23:42, 2016. URL: http://eccc.hpi-web.de/report/2016/042.
  12. Oded Goldreich and Tom Gur. Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP. Electronic Colloquium on Computational Complexity (ECCC), 23:192, 2016. URL: http://eccc.hpi-web.de/report/2016/192.
  13. Oded Goldreich, Tom Gur, and Ilan Komargodski. Strong locally testable codes with relaxed local decoders. In David Zuckerman, editor, 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA, volume 33 of LIPIcs, pages 1-41. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.1.
  14. Oded Goldreich and Madhu Sudan. Locally testable codes and pcps of almost-linear length. J. ACM, 53(4):558-655, 2006. URL: http://dx.doi.org/10.1145/1162349.1162351.
  15. Tom Gur, Govind Ramnarayan, and Ron Rothblum. Relaxed locally correctable codes. Electronic Colloquium on Computational Complexity (ECCC), 24:143, 2017. URL: https://eccc.weizmann.ac.il/report/2017/143.
  16. Tom Gur and Ron D. Rothblum. Non-interactive proofs of proximity. Computational Complexity, pages 1-109, 2016. URL: http://dx.doi.org/10.1007/s00037-016-0136-9.
  17. Richard W Hamming. Error detecting and error correcting codes. Bell Labs Technical Journal, 29(2):147-160, 1950. Google Scholar
  18. Brett Hemenway, Noga Ron-Zewi, and Mary Wootters, 2017. Personal communication. Google Scholar
  19. Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 202-215. ACM, 2016. URL: http://dx.doi.org/10.1145/2897518.2897523.
  20. Swastik Kopparty and Shubhangi Saraf. Local testing and decoding of high-rate error-correcting codes. Electronic Colloquium on Computational Complexity (ECCC), 24:126, 2017. URL: https://eccc.weizmann.ac.il/report/2017/126.
  21. Or Meir. Combinatorial construction of locally testable codes. SIAM J. Comput., 39(2):491-544, 2009. URL: http://dx.doi.org/10.1137/080729967.
  22. Or Meir. Combinatorial pcps with short proofs. Computational Complexity, 25(1):1-102, 2016. URL: http://dx.doi.org/10.1007/s00037-015-0111-x.
  23. Dana Moshkovitz and Ran Raz. Two-query pcp with subconstant error. Journal of the ACM (JACM), 57(5):29, 2010. Google Scholar
  24. Claude Elwood Shannon. Communication in the presence of noise. Proceedings of the IRE, 37(1):10-21, 1949. Google Scholar
  25. Sergey Yekhanin. Towards 3-query locally decodable codes of subexponential length. J. ACM, 55(1):1:1-1:16, 2008. URL: http://dx.doi.org/10.1145/1326554.1326555.
  26. Sergey Yekhanin. Locally decodable codes. Foundations and Trends in Theoretical Computer Science, 6(3):139-255, 2012. URL: http://dx.doi.org/10.1561/0400000030.
  27. Victor Vasilievich Zyablov. An estimate of the complexity of constructing binary linear cascade codes. Problemy Peredachi Informatsii, 7(1):5-13, 1971. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact