research-article

High-rate codes with sublinear-time decoding

Authors:

Swastik Kopparty,

Shubhangi Saraf,

Sergey YekhaninAuthors Info & Claims

Journal of the ACM (JACM), Volume 61, Issue 5

Article No.: 28, Pages 1 - 20

https://doi.org/10.1145/2629416

Published: 08 September 2014 Publication History

Abstract

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms; any bit of the original message can be recovered by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a code and the locality/efficiency of its decoding algorithms has been well studied, and it has widely been suspected that nontrivial locality must come at the price of low rate. A particular setting of potential interest in practice is codes of constant rate. For such codes, decoding algorithms with locality O(k∈) were known only for codes of rate ∈Ω(1/∈), where k is the length of the message. Furthermore, for codes of rate > 1/2, no nontrivial locality had been achieved.

In this article, we construct a new family of locally decodable codes that have very efficient local decoding algorithms, and at the same time have rate approaching 1. We show that for every ∈ > 0 and α > 0, for infinitely many k, there exists a code C which encodes messages of length k with rate 1 − α, and is locally decodable from a constant fraction of errors using O(k∈) queries and time.

These codes, which we call multiplicity codes, are based on evaluating multivariate polynomials and their derivatives. Multiplicity codes extend traditional multivariate polynomial codes; they inherit the local-decodability of these codes, and at the same time achieve better tradeoffs and flexibility in the rate and minimum distance.

References

[1]

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. 1998. Proof verification and the hardness of approximation problems. J. ACM 45, 3 (May 1998), 501--555.

Digital Library

[2]

Sanjeev Arora and Shmuel Safra. 1998. Probabilistic checking of proofs: A new characterization of NP. J. ACM 45, 1, 70--122.

Digital Library

[3]

Sanjeev Arora and Madhu Sudan. 2003. Improved low-degree testing and its applications. Combinatorica 23, 365--426.

[4]

Laszlo Babai, Lance Fortnow, Leonid Levin, and Mario Szegedy. 1991a. Checking computations in polylogarithmic time. In Proceedings of the 23rd ACM Symposium on Theory of Computing (STOC). 21--31.

Digital Library

[5]

László Babai, Lance Fortnow, and Carsten Lund. 1991b. Non-deterministic exponential time has two-prover interactive protocols. Computat. Complex. 1, 1, 3--40.

[6]

Laszlo Babai, Lance Fortnow, Naom Nisan, and Avi Wigderson. 1993. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computat. Complex. 3, 307--318.

Digital Library

[7]

Donald Beaver and Joan Feigenbaum. 1990. Hiding instances in multioracle queries. In Proceedings of the 7th International Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 415, Springer, Berlin, 37--48.

Digital Library

[8]

Avraham Ben-Aroya, Klim Efremenko, and Amnon Ta-Shma. 2010. Local list decoding with a constant number of queries. In Proceedings of the 51st IEEE Symposium on Foundations of Computer Science (FOCS).

Digital Library

[9]

Y. Meng Chee, T. Feng, S. Ling, H. Wang, and L. F. Zhang. 2010. Query-efficient locally decodable codes of subexponential length. Arxiv 1008.1617.

Digital Library

[10]

A. Deshpande, R. Jain, T. Kavitha, S. Lokam, and J. Radhakrishnan. 2002. Better lower bounds for locally decodable codes. In Proceedings of the 20th IEEE Computational Complexity Conference (CCC). 184--193.

Digital Library

[11]

Zeev Dvir. 2010. On matrix rigidity and locally self-correctable codes. In Proceedings of the 26th IEEE Computational Complexity Conference (CCC). 102--113.

Digital Library

[12]

Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin. 2010. Matching vector codes. In Proceedings of the 51st IEEE Symposium on Foundations of Computer Science (FOCS).

Digital Library

[13]

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan. 2009. Extensions to the method of multiplicities, with applications to kakeya sets and mergers. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS). 181--190.

Digital Library

[14]

Klim Efremenko. 2009. 3-query locally decodable codes of subexponential length. In Proceedings of the 41st ACM Symposium on Theory of Computing (STOC). 39--44.

Digital Library

[15]

Oded Goldreich, Howard Karloff, Leonard Schulman, and Luca Trevisan. 2002. Lower bounds for locally decodable codes and private information retrieval. In Proceedings of the 17th IEEE Computational Complexity Conference (CCC). 175--183.

Digital Library

[16]

Alan Guo. 2013. High rate locally correctable codes via lifting. Electron. Colloq. Computat. Complex. (ECCC) 20, 53.

[17]

Alan Guo, Swastik Kopparty, and Madhu Sudan. 2013. New affine-invariant codes from lifting. In Proceedings of the ITCS. 529--540.

Digital Library

[18]

Venkatesan Guruswami and Atri Rudra. 2008. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Trans. Inf. Theory 54, 1, 135--150.

Digital Library

[19]

Venkatesan Guruswami, Amit Sahai, and Madhu Sudan. 2000. Soft-decision decoding of Chinese remainder codes. In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (Redondo Beach, Cal.), 159--168.

Digital Library

[20]

Venkatesan Guruswami and Madhu Sudan. 1999. Improved decoding of Reed-Solomon and Algebraic-geometric codes. IEEE Trans. Inf. Theory 45, 1757--1767.

Digital Library

[21]

Venkatesan Guruswami and Carol Wang. 2011. Optimal rate list decoding via derivative codes. In Proceedings of the APPROX-RANDOM. 593--604.

Digital Library

[22]

Brett Hemenway, Rafail Ostrovsky, and Mary Wootters. 2013. Local correctability of expander codes. In Proceedings of the ICALP (1). 540--551.

Digital Library

[23]

J. W. P. Hirschfeld, G. Korchmaros, and F. Torres. 2008. Algebraic Curves over a Finite Field. Princeton Series in Applied Mathematics, Princeton University Press.

[24]

Russell Impagliazzo and Avi Wigderson. 1997. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 220--229.

Digital Library

[25]

Toshiya Itoh and Yasuhiro Suzuki. 2010. New constructions for query-efficient locally decodable codes of subexponential length. IEICE Trans. Inf. Syst. E93-D, 263--270.

[26]

Tadao Kasami, Shu Lin, and W. Peterson. 1968. New generalizations of the Reed-Muller codes -- I: Primitive codes. Proceedings of the Information Theory, IEEE Trans. 14, 2, 189--199.

Digital Library

[27]

Jonathan Katz and Luca Trevisan. 2000. On the efficiency of local decoding procedures for error-correcting codes. In Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC). 80--86.

Digital Library

[28]

Iordanis Kerenidis and Ronald de Wolf. 2004. Exponential lower bound for 2-query locally decodable codes via a quantum argument. J. Comput. Syst. Sci. 69, 395--420.

Digital Library

[29]

Swastik Kopparty. 2012. List-decoding multiplicity codes. Electron. Colloq. Computat. Complex. (TR12-044).

[30]

Swastik Kopparty. 2014. Some remarks on multiplicity codes. In Proceedings of the AMS Special Session on Discrete Geometry and Algebraic Combinatorics (Contemporary Mathematics).

[31]

Richard Lipton. 1990. Efficient checking of computations. In Proceedings of the 7th International Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 415, Springer, Berlin, 207--215.

Digital Library

[32]

Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. 1992. Algebraic methods for interactive proof systems. J. ACM 39, 4, 859--868.

Digital Library

[33]

F. J. MacWilliams and N. J. A. Sloane. 1977. The Theory of Error Correcting Codes. North Holland, Amsterdam, The Netherlands.

[34]

Kenji Obata. 2002. Optimal lower bounds for 2-query locally decodable linear codes. In Proceedings of the 6th International Workshop on Randomization and Computation (RANDOM), Lecture Notes in Computer Science, vol. 2483, Springer, Berlin, 39--50.

Digital Library

[35]

Farzad Parvaresh and Alexander Vardy. 2005. Correcting errors beyond the Guruswami-Sudan radius in polynomial time. In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS). 285--294.

Digital Library

[36]

Prasad Raghavendra. 2007. A Note on Yekhanin’s locally decodable codes. Electron. Colloq. Computat. Complex. (TR07-016).

[37]

Irving S. Reed. 1954. A class of multiple-error-correcting codes and the decoding scheme. IEEE Trans. Inf. Theory 4, 38--49.

[38]

Shubhangi Saraf and Madhu Sudan. 2008. Improved lower bound on the size of Kakeya sets over finite fields. Analysis and PDE.

[39]

Ronen Shaltiel and Christopher Umans. 2005. Simple extractors for all min-entropies and a new pseudorandom generator. J. ACM 52, 2, 172--216.

Digital Library

[40]

Adi Shamir. 1992. IP = PSPACE. J. ACM 39, 4, 869--877.

Digital Library

[41]

Madhu Sudan. 2001. Ideal error-correcting codes: Unifying algebraic and number-theoretic algorithms. In Proceedings of the AAECC. 36--45.

Digital Library

[42]

Madhu Sudan, Luca Trevisan, and Salil Vadhan. 1999. Pseudorandom generators without the XOR lemma. In Proceedings of the 39th ACM Symposium on Theory of Computing (STOC). 537--546.

Digital Library

[43]

Stephanie Wehner and Ronald de Wolf. 2005. Improved lower bounds for locally decodable codes and private information retrieval. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 3580, Springer, Berlin, 1424--1436.

Digital Library

[44]

Lloyd R. Welch and Elwyn R. Berlekamp. 1986. Error correction for algebraic block codes. US Patent 4,633,470.

[45]

David Woodruff. 2007. New lower bounds for general locally decodable codes. Electron. Colloq. Computat. Complex. (TR07-006).

[46]

David Woodruff and Sergey Yekhanin. 2005. A geometric approach to information theoretic private information retrieval. In Proceedings of the 20th IEEE Computational Complexity Conference (CCC). 275--284.

Digital Library

[47]

Chaoping Xing. 2003. Nonlinear codes from algebraic curves improving the Tsfasman-Vladut-Zink bound. IEEE Trans. Inf. Theory 49, 7, 1653--1657.

Digital Library

[48]

Sergey Yekhanin. 2008. Towards 3-query locally decodable codes of subexponential length. J. ACM 55, 1--16.

Digital Library

[49]

Sergey Yekhanin. 2012. Locally decodable codes. Found. Trends Theoret. Comput. Sci. 6, 3, 139--255.

Digital Library

Cited By

Ron-Zewi NRothblum R(2024)Local Proofs Approaching the Witness LengthJournal of the ACM10.1145/366148371:3(1-42)Online publication date: 25-Apr-2024
https://dl.acm.org/doi/10.1145/3661483
Kothari PManohar PMohar BShinkar IO'Donnell R(2024)An Exponential Lower Bound for Linear 3-Query Locally Correctable CodesProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649640(776-787)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649640
Kumar VMon GMohar BShinkar IO'Donnell R(2024)Relaxed Local Correctability from Local TestingProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649611(1585-1593)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649611
Show More Cited By

Index Terms

High-rate codes with sublinear-time decoding
1. Mathematics of computing
  1. Information theory
    1. Coding theory
2. Security and privacy
  1. Cryptography
    1. Mathematical foundations of cryptography

Recommendations

High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity

Locally correctable codes (LCCs) and locally testable codes (LTCs) are error-correcting codes that admit local algorithms for correction and detection of errors. Those algorithms are local in the sense that they only query a small number of entries of ...
High-rate codes with sublinear-time decoding
STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms; any bit of the original message can be recovered by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a code ...
A new family of locally correctable codes based on degree-lifted algebraic geometry codes
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry base-code of block-length q to a lifted-code of block-length q^m, for arbitrary integer m. The construction generalizes the way degree-d, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 61, Issue 5

August 2014

171 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/2668245

Editor:
Victor Vianu
University of California, San Diego

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 September 2014

Accepted: 01 January 2014

Revised: 01 January 2014

Received: 01 April 2013

Published in JACM Volume 61, Issue 5

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
756
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)7

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ron-Zewi NRothblum R(2024)Local Proofs Approaching the Witness LengthJournal of the ACM10.1145/366148371:3(1-42)Online publication date: 25-Apr-2024
https://dl.acm.org/doi/10.1145/3661483
Kothari PManohar PMohar BShinkar IO'Donnell R(2024)An Exponential Lower Bound for Linear 3-Query Locally Correctable CodesProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649640(776-787)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649640
Kumar VMon GMohar BShinkar IO'Donnell R(2024)Relaxed Local Correctability from Local TestingProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649611(1585-1593)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649611
Bhandari SHarsha PKumar MSudan M(2024)Ideal-Theoretic Explanation of Capacity-Achieving DecodingIEEE Transactions on Information Theory10.1109/TIT.2023.334589070:2(1107-1123)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TIT.2023.3345890
Bhandari SHarsha PKumar MSudan M(2024)Decoding Multivariate Multiplicity Codes on Product SetsIEEE Transactions on Information Theory10.1109/TIT.2023.330684970:1(154-169)Online publication date: Jan-2024
https://doi.org/10.1109/TIT.2023.3306849
Sajjad MShah T(2024)Decoding of cyclic codes over quaternion integers by modified Berlekamp–Massey algorithmComputational and Applied Mathematics10.1007/s40314-023-02442-343:2Online publication date: 29-Feb-2024
https://doi.org/10.1007/s40314-023-02442-3
Kopparty SRon-Zewi NSaraf SWootters M(2023)Improved List Decoding of Folded Reed-Solomon and Multiplicity CodesSIAM Journal on Computing10.1137/20M137021552:3(794-840)Online publication date: 15-Jun-2023
https://doi.org/10.1137/20M1370215
Guerrini ELairedj KLebreton RZappatore I(2023)Simultaneous Rational Function Reconstruction with errorsJournal of Symbolic Computation10.1016/j.jsc.2022.10.007116:C(345-364)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1016/j.jsc.2022.10.007
Cohen GYankovitz T(2022)Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS54457.2022.00010(24-35)Online publication date: Oct-2022
https://doi.org/10.1109/FOCS54457.2022.00010
Blocki JCheng KGrigorescu ELi XZheng YZhu M(2022)Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00077(739-750)Online publication date: Feb-2022
https://doi.org/10.1109/FOCS52979.2021.00077
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents