research-article

Free access

High-rate codes with sublinear-time decoding

Authors:

Swastik Kopparty,

Shubhangi Saraf,

Sergey YekhaninAuthors Info & Claims

STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

Pages 167 - 176

https://doi.org/10.1145/1993636.1993660

Published: 06 June 2011 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 exp(1/ε), where k is the length of the message. Furthermore, for codes of rate > 1/2, no nontrivial locality has been achieved.

In this paper 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. The high rate and local decodability are evident even in concrete settings (and not just in asymptotic behavior), giving hope that local decoding techniques may have practical implications.

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

Supplementary Material

JPG File (stoc_3b_2.jpg)

Download
15.63 KB

MP4 File (stoc_3b_2.mp4)

Download
99.08 MB

References

[1]

S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501--555, May 1998.

Digital Library

[2]

S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1):70--122, January 1998.

Digital Library

[3]

S. Arora and M. Sudan. Improved low-degree testing and its applications. Combinatorica, 23:365--426, 2003.

[4]

L. Babai, L. Fortnow, L. Levin, and M. Szegedy. Checking computations in polylogarithmic time. In 23rd ACM Symposium on Theory of Computing (STOC), pages 21--31, 1991.

Digital Library

[5]

L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1(1):3--40, 1991.

[6]

L. Babai, L. Fortnow, N. Nisan, and A. Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3:307--318, 1993.

Digital Library

[7]

D. Beaver and J. Feigenbaum. Hiding instances in multioracle queries. In 7th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 415 of Lecture Notes in Computer Science, pages 37--48. Springer, Berlin, Heidelberg, 1990.

Digital Library

[8]

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

Digital Library

[9]

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

Digital Library

[10]

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

Digital Library

[11]

Z. Dvir. On matrix rigidity and locally self-correctable codes. In 26th IEEE Computational Complexity Conference (CCC), pages 102--113, 2010.

Digital Library

[12]

Z. Dvir, P. Gopalan, and S. Yekhanin. Matching vector codes. In 51st IEEE Symposium on Foundations of Computer Science (FOCS), 2010.

Digital Library

[13]

Z. Dvir, S. Kopparty, S. Saraf, and M. Sudan. Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. In 50th IEEE Symposium on Foundations of Computer Science (FOCS), pages 181--190, 2009.

Digital Library

[14]

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

Digital Library

[15]

O. Goldreich, H. Karloff, L. Schulman, and L. Trevisan. Lower bounds for locally decodable codes and private information retrieval. In 17th IEEE Computational Complexity Conference (CCC), pages 175--183, 2002.

Digital Library

[16]

V. Guruswami and A. Rudra. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Transactions on Information Theory, 54(1):135--150, 2008.

Digital Library

[17]

V. Guruswami, A. Sahai, and M. Sudan. Soft-decision decoding of Chinese Remainder codes. In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, pages 159--168, Redondo Beach, California, 12--14 November 2000.

Digital Library

[18]

V. Guruswami and M. Sudan. Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Transactions on Information Theory, 45:1757--1767, 1999.

Digital Library

[19]

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

[20]

R. Impagliazzo and A. Wigderson. P= BPP if E requires exponential circuits: Derandomizing the XOR Lemma. Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 220--229, May 1997.

Digital Library

[21]

T. Itoh and Y. Suzuki. New constructions for query-efficient locally decodable codes of subexponential length. IEICE Transactions on Information and Systems, pages 263--270, 2010.

[22]

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

Digital Library

[23]

I. Kerenidis and R. de Wolf. Exponential lower bound for 2-query locally decodable codes via a quantum argument. Journal of Computer and System Sciences, 69:395--420, 2004.

Digital Library

[24]

R. Lipton. Efficient checking of computations. In 7th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 415 of Lecture Notes in Computer Science, pages 207--215. Springer, Berlin, Heidelberg, 1990.

Digital Library

[25]

C. Lund, L. Fortnow, H. J. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4):859--868, October 1992.

Digital Library

[26]

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

Digital Library

[27]

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

Digital Library

[28]

P. Raghavendra. A note on Yekhanin's locally decodable codes. In Electronic Colloquium on Computational Complexity (ECCC), TR07-016, 2007.

[29]

I. S. Reed. A class of multiple-error-correcting codes and the decoding scheme. IEEE Transactions on Information Theory, 4:38--49, 1954.

[30]

M. Rozenbloom and M. Tsfasman. Codes for the m-metric. Problems Inform. Transmission, 33:45--52, 1997.

[31]

S. Saraf and M. Sudan. Improved lower bound on the size of Kakeya sets over finite fields. Analysis and PDE, 2008.

[32]

R. Shaltiel and C. Umans. Simple extractors for all min-entropies and a new pseudorandom generator. J. ACM, 52(2):172--216, 2005.

Digital Library

[33]

A. Shamir. IP = PSPACE. Journal of the ACM, 39(4):869--877, October 1992.

Digital Library

[34]

M. Sudan. Ideal error-correcting codes: Unifying algebraic and number-theoretic algorithms. In AAECC, pages 36--45, 2001.

Digital Library

[35]

M. Sudan, L. Trevisan, and S. Vadhan. Pseudorandom generators without the XOR lemma. In 39th ACM Symposium on Theory of Computing (STOC), pages 537--546, 1999.

Digital Library

[36]

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

Digital Library

[37]

D. Woodruff. New lower bounds for general locally decodable codes. In Electronic Colloquium on Computational Complexity (ECCC), TR07-006, 2007.

[38]

D. Woodruff and S. Yekhanin. A geometric approach to information theoretic private information retrieval. In 20th IEEE Computational Complexity Conference (CCC), pages 275--284, 2005.

Digital Library

[39]

C. Xing. Nonlinear codes from algebraic curves improving the Tsfasman-Vladut-Zink bound. IEEE Transactions on Information Theory, 49(7):1653--1657, 2003.

Digital Library

[40]

S. Yekhanin. Towards $3$-query locally decodable codes of subexponential length. Journal of the ACM, 55:1--16, 2008.

Digital Library

[41]

S. Yekhanin. Locally decodable codes. Foundations and trends in theoretical computer science, 2010. to appear.

Digital Library

Cited By

Vardy AYaakobi E(2023)Private Information Retrieval Without Storage Overhead: Coding Instead of ReplicationIEEE Journal on Selected Areas in Information Theory10.1109/JSAIT.2023.32856654(286-301)Online publication date: 2023
https://doi.org/10.1109/JSAIT.2023.3285665
Levy-dit-Vehel FRoméas M(2023)A Framework for the Design of Secure and Efficient Proofs of RetrievabilityCryptography, Codes and Cyber Security10.1007/978-3-031-23201-5_6(83-103)Online publication date: 1-Jan-2023
https://doi.org/10.1007/978-3-031-23201-5_6
Weng CYakimenka YLin HRosnes EKliewer J(2022)Generative Adversarial User Privacy in Lossy Single-Server Information RetrievalIEEE Transactions on Information Forensics and Security10.1109/TIFS.2022.320332017(3495-3510)Online publication date: 2022
https://doi.org/10.1109/TIFS.2022.3203320
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 codes with sublinear-time decoding

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 ...
Optimal rate list decoding via derivative codes
APPROX'11/RANDOM'11: Proceedings of the 14th international workshop and 15th international conference on Approximation, randomization, and combinatorial optimization: algorithms and techniques

The classical family of [n, k]_q Reed-Solomon codes over a field F_q consist of the evaluations of polynomials f ∈ F_q[X] of degree < k at n distinct field elements. In this work, we consider a closely related family of codes, called (order m) derivative ...
Symbol-by-symbol MAP decoding algorithm for high-rate convolutional codes that use reciprocal dual codes

A symbol-by-symbol maximum a posteriori (MAP) decoding algorithm for high-rate convolutional codes applying reciprocal dual convolutional codes is presented. The advantage of this approach is a reduction of the computational complexity since the number ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

June 2011

840 pages

ISBN:9781450306911

DOI:10.1145/1993636

General Chair:
Lance Fortnow
Northwestern University
,
Program Chair:
Salil Vadhan
Harvard University

Copyright © 2011 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 ACM 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]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'11

Sponsor:

SIGACT

STOC'11: Symposium on Theory of Computing

June 6 - 8, 2011

California, San Jose, USA

Acceptance Rates

STOC '11 Paper Acceptance Rate 84 of 304 submissions, 28%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
515
Total Downloads

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

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Vardy AYaakobi E(2023)Private Information Retrieval Without Storage Overhead: Coding Instead of ReplicationIEEE Journal on Selected Areas in Information Theory10.1109/JSAIT.2023.32856654(286-301)Online publication date: 2023
https://doi.org/10.1109/JSAIT.2023.3285665
Levy-dit-Vehel FRoméas M(2023)A Framework for the Design of Secure and Efficient Proofs of RetrievabilityCryptography, Codes and Cyber Security10.1007/978-3-031-23201-5_6(83-103)Online publication date: 1-Jan-2023
https://doi.org/10.1007/978-3-031-23201-5_6
Weng CYakimenka YLin HRosnes EKliewer J(2022)Generative Adversarial User Privacy in Lossy Single-Server Information RetrievalIEEE Transactions on Information Forensics and Security10.1109/TIFS.2022.320332017(3495-3510)Online publication date: 2022
https://doi.org/10.1109/TIFS.2022.3203320
Ishai YLai RMalavolta G(2021)A Geometric Approach to Homomorphic Secret SharingPublic-Key Cryptography – PKC 202110.1007/978-3-030-75248-4_4(92-119)Online publication date: 10-May-2021
https://dl.acm.org/doi/10.1007/978-3-030-75248-4_4
Skachek V(2018)Batch and PIR Codes and Their Connections to Locally Repairable CodesNetwork Coding and Subspace Designs10.1007/978-3-319-70293-3_16(427-442)Online publication date: 30-Jan-2018
https://doi.org/10.1007/978-3-319-70293-3_16
Asi HYaakobi E(2017)Nearly optimal constructions of PIR and batch codes2017 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT.2017.8006508(151-155)Online publication date: Jun-2017
https://doi.org/10.1109/ISIT.2017.8006508
Dachman-Soled DKulkarni MShahverdi A(2017)Tight Upper and Lower Bounds for Leakage-Resilient, Locally Decodable and Updatable Non-malleable CodesPublic-Key Cryptography – PKC 201710.1007/978-3-662-54365-8_13(310-332)Online publication date: 26-Feb-2017
https://doi.org/10.1007/978-3-662-54365-8_13
Ben-Sasson EKaplan YKopparty SMeir OStichtenoth H(2016)Constant Rate PCPs for Circuit-SAT with Sublinear Query ComplexityJournal of the ACM10.1145/290129463:4(1-57)Online publication date: 8-Nov-2016
https://dl.acm.org/doi/10.1145/2901294
Zhou WLin SAbdel-Ghaffar K(2016)BCH Codes for the Rosenbloom–Tsfasman MetricIEEE Transactions on Information Theory10.1109/TIT.2016.261731262:12(6757-6767)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1109/TIT.2016.2617312
Guo AKopparty S(2016)List-Decoding Algorithms for Lifted CodesIEEE Transactions on Information Theory10.1109/TIT.2016.253876662:5(2719-2725)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1109/TIT.2016.2538766
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Publication

Media

Figures

Other

Tables

View Table of Contents