research-article

Public Access

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

Authors:

Swastik Kopparty,

Shubhangi SarafAuthors Info & Claims

Journal of the ACM (JACM), Volume 64, Issue 2

Article No.: 11, Pages 1 - 42

https://doi.org/10.1145/3051093

Published: 25 May 2017 Publication History

Abstract

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 the corrupted codeword. The fundamental question about LCCs and LTCs is to determine the optimal tradeoff among their rate, distance, and query complexity.

In this work, we construct the first LCCs and LTCs with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist LCCs and LTCs with block length n, constant rate (which can even be taken arbitrarily close to 1), and constant relative distance, whose query complexity is exp(Õ(√log n)) (for LCCs) and (log n)^{O(log log n)} (for LTCs).

In addition to having small query complexity, our codes also achieve better tradeoffs between the rate and the relative distance than were previously known to be achievable by LCCs or LTCs. Specifically, over large (but constant size) alphabet, our codes approach the Singleton bound, that is, they have almost the best-possible relationship between their rate and distance. Over the binary alphabet, our codes meet the Zyablov bound. Such tradeoffs between the rate and the relative distance were previously not known for any o(n) query complexity. Our results on LCCs also immediately give locally decodable codes with the same parameters.

References

[1]

Noga Alon, Jehoshua Bruck, Joseph Naor, Moni Naor, and Ron M. Roth. 1992. Construction of asymptotically good low rate error-correcting codes through pseudo-random graphs. IEEE Trans. Inf. Theor. 38 (1992), 509--516.

Digital Library

[2]

Noga Alon and Fan R. K. Chung. 1988. Explicit construction of linear sized tolerant networks. Discr. Math. 72, 1--3 (1988), 15--19.

Digital Library

[3]

Noga Alon, Jeff Edmonds, and Michael Luby. 1995. Linear time erasure codes with nearly optimal recovery. In Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS’95). IEEE Computer Society, 512--519.

Digital Library

[4]

Noga Alon and Michael Luby. 1996. A linear time erasure-resilient code with nearly optimal recovery. IEEE Trans. Inf. Theor. 42, 6 (1996), 1732--1736.

[5]

N. Alon and V. D. Milman. 1985. λ₁, Isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theor. Ser. B 38, 1 (1985), 73--88.

[6]

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

Digital Library

[7]

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

Digital Library

[8]

László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. 1991. Checking computations in polylogarithmic time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC’91). ACM Press, 21--31. http://doi.acm.org/10.1145/103418.103428

Digital Library

[9]

László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson. 1993. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Comput. Complex. 3, 4 (1993), 307--318.

Digital Library

[10]

Eli Ben-Sasson and Madhu Sudan. 2006. Robust locally testable codes and products of codes. Random Struct. Algor. 28, 4 (2006), 387--402.

Digital Library

[11]

Eli Ben-Sasson and Madhu Sudan. 2008. Short PCPs with polylog query complexity. SIAM J. Comput. 38, 2 (2008), 551--607.

Digital Library

[12]

Eli Ben-Sasson and Michael Viderman. 2009. Tensor products of weakly smooth codes are robust. Theor. Comput. 5, 1 (2009), 239--255.

[13]

Eli Ben-Sasson and Michael Viderman. 2012. Towards lower bounds on locally testable codes via density arguments. Comput. Complex. 21, 2 (2012), 267--309.

Digital Library

[14]

Eli Ben-Sasson and Michael Viderman. 2015. Composition of semi-LTCs by two-wise tensor products. Computat. Complex. 24, 3 (2015), 601--643. http://dx.doi.org/10.1007/s00037-013-0074-8

Digital Library

[15]

Manuel Blum and Sampath Kannan. 1995. Designing programs that check their work. J. ACM 42, 1 (1995), 269--291.

Digital Library

[16]

Manuel Blum, Michael Luby, and Ronitt Rubinfeld. 1993. Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47, 3 (1993), 549--595.

Digital Library

[17]

Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan. 1998. Private information retrieval. J. ACM 45, 6 (1998), 965--981.

Digital Library

[18]

Don Coppersmith and Atri Rudra. 2005. On the robust testability of tensor products of codes. Electronic Colloquium on Computational Complexity (ECCC) 104 (2005).

[19]

Irit Dinur. 2007. The PCP theorem by gap amplification. J. ACM 54, 3 (2007), 241--250.

Digital Library

[20]

Irit Dinur and Tali Kaufman. 2011. Dense locally testable codes cannot have constant rate and distance. In Proceedings of the 14th International Workshop on Randomization and Computation (RANDOM’11). Springer, 507--518.

[21]

Irit Dinur, Madhu Sudan, and Avi Wigderson. 2006. Robust local testability of tensor products of LDPC codes. In Proceedings of the 9th International Workshop on Randomization and Computation (RANDOM’06). Springer, 304--315.

Digital Library

[22]

Jozef Dodziuk. 1984. Difference equations, Isoperimetric inequality and transience of certain random walks. Trans. Am. Math. Soc. 284, 2 (1984), 787--794.

[23]

Klim Efremenko. 2012. 3-query locally decodable codes of subexponential length. SIAM J. Comput. 41, 6 (2012), 1694--1703.

Digital Library

[24]

David Forney. 1966. Generalized minimum distance decoding. IEEE Trans. Inf. Theor. 12, 2 (1966), 125--131.

Digital Library

[25]

Katalin Friedl and Madhu Sudan. 1995. Some improvements to total degree tests. In Proceedings of the 3rd Israel Symposium on the Theory of Computing and Systems (ISTC’95S). IEEE Computer Society, 190--198.

[26]

Ofer Gabber and Zvi Galil. 1981. Explicit constructions of linear-sized superconcentrators. J. Comput. Syst. Sci. 22, 3 (1981), 407--420.

[27]

Edgar N. Gilbert. 1952. A comparision of signalling alphabets. Bell Syst. Techn. J. 31 (1952), 504--522.

[28]

Oded Goldreich. 2011. Bravely, moderately: A common theme in four recent works. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. Springer, 373--389.

Digital Library

[29]

Oded Goldreich and Or Meir. 2012. The tensor product of two good codes is not necessarily locally testable. Inf. Proces. Lett. 112, 8-9 (2012), 351--355.

Digital Library

[30]

Oded Goldreich and Madhu Sudan. 2006. Locally testable codes and PCPs of almost linear length. J. ACM 53, 4 (2006), 558--655.

Digital Library

[31]

Alan Guo, Swastik Kopparty, and Madhu Sudan. 2013. New affine-invariant codes from lifting. In proceedings of the Innovations in Theoretical Computer Science Conference (ITCS). ACM Press, 529--540.

Digital Library

[32]

Venkatesan Guruswami and Piotr Indyk. 2002. Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC’02). ACM Press, 812--821.

Digital Library

[33]

Venkatesan Guruswami and Piotr Indyk. 2005. Linear-time encodable/decodable codes with near-optimal rate. IEEE Trans. Inf. Theor. 51, 10 (2005), 3393--3400.

Digital Library

[34]

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

Digital Library

[35]

Richard W. Hamming. 1950. Error detecting and error correcting codes. Bell Syst. Techn. J. 29, 2 (1950), 147--160.

[36]

Brett Hemenway, Rafail Ostrovsky, and Mary Wootters. 2015. Local correctability of expander codes. Inf. Comput. 243 (2015), 178--190. http://dx.doi.org/10.1016/j.ic.2014.12.013

Digital Library

[37]

Brett Hemenway and Mary Wootters. 2015. Linear-time list recovery of high-rate expander codes. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP’15). Springer, 701--712.

[38]

Shlomo Hoory, Nati Linial, and Avi Wigderson. 2006. Expander graphs and their applications. Bull. AMS 43, 4 (2006), 439--561.

[39]

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

Digital Library

[40]

Kiran S. Kedlaya and Sergey Yekhanin. 2009. Locally decodable codes from nice subsets of finite fields and prime factors of Mersenne numbers. SIAM J. Comput. 38, 5 (2009), 1952--1969.

Digital Library

[41]

S. Kopparty. 2012. List-decoding multiplicity codes. In Electronic Colloquium on Computational Complexity (ECCC)(TR12-044).

[42]

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

[43]

Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. 2015a. High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. Electronic Colloquium on Computational Complexity (ECCC) (2015).

[44]

Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. 2015b. High-rate locally-testable codes with quasi-polylogarithmic query complexity. Electronic Colloquium on Computational Complexity (ECCC) (2015).

[45]

Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin. 2014. High-rate codes with sublinear-time decoding. J. ACM 61, 5 (2014), 28.

Digital Library

[46]

Richard J. Lipton. 1990. Efficient checking of computations. In Proceedings of the 7th Annual ACM Symposium on Theoretical Aspects of Computer Science (STACS’90). LCNS, Vol. 415. Springer, 207--215.

[47]

Or Meir. 2009. Combinatorial construction of locally testable codes. SIAM J. Comput. 39, 2 (2009), 491--544.

Digital Library

[48]

Or Meir. 2012. On the rectangle method in proofs of robustness of tensor products. Inf. Process. Lett. 112, 6 (2012), 257--260.

Digital Library

[49]

Or Meir. 2014. Locally correctable and testable codes approaching the Singleton bound. Electronic Colloquium on Computational Complexity (ECCC) 21 (2014), 107.

[50]

Prasad Raghavendra. 2007. A note on Yekhanin’s locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC) 14, 016 (2007).

[51]

Irving S. Reed and Gustave Solomon. 1960. Polynomial codes over certain finite fields. SIAM J. Soc. Industr. Appl. Math. 8, 2 (1960), 300--304.

[52]

Omer Reingold. 2008. Undirected connectivity in log-space. J. ACM 55, 4 (2008), 17:1--17:24. http://doi.acm.org/10.1145/1391289.1391291

Digital Library

[53]

Omer Reingold, Salil Vadhan, and Avi Wigderson. 2002. Entropy waves, the zig-zag graph product, and new constant-degree expanders. Ann. Math. 155, 1 (2002), 157--187.

[54]

Ronitt Rubinfeld and Madhu Sudan. 1996. Robust characterization of polynomials with applications to program testing. SIAM J. Comput. 25, 2 (1996), 252--271.

Digital Library

[55]

Claude E. Shannon. 2001. Originally appeared in Bell System Tech. J. 27:379--423, 623--656, 1948. A mathematical theory of communication. ACM SIGMOBILE Mobile Computing and Communications Review 5, 1 (2001), 3--55.

[56]

Richard C. Singleton. 1964. Maximum distance q-nary codes. IEEE Trans. Inf. Theor. 10, 2 (1964), 116--118.

Digital Library

[57]

Madhu Sudan. 2001. Algorithmic introduction to coding theory (Lecture notes). Available at http://people.csail.mit.edu/madhu/FT01/.

[58]

Madhu Sudan, Luca Trevisan, and Salil P. Vadhan. 2001. Pseudorandom Generators without the XOR lemma. J. Comput. Syst. Sci. 62, 2 (2001), 236--266.

Digital Library

[59]

Luca Trevisan. 2003. List-decoding using the XOR lemma. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS’03). IEEE Computer Society, 126--135.

[60]

Paul Valiant. 2005. The tensor product of two codes is not necessarily robustly testable. In Proceedings of the 9th International Workshop on Randomization and Computation (RANDOM’05). Springer, 472--481.

Digital Library

[61]

R. R. Varshamov. 1957. Estimate of the number of signals in error correcting codes. Dokl. Akad. Nauk 117 (1957), 739--741.

[62]

Michael Viderman. 2013a. Strong LTCs with inverse poly-log rate and constant soundness. In Proceedings of the 54th IEEE Symposium on Foundations of Computer Science (FOCS'13). IEEE Computer Society, 330--339.

Digital Library

[63]

Michael Viderman. 2013b. Strong LTCs with inverse polylogarithmic rate and soundness. In Proceedings of the 28th Conference on Computational Complexity (CCC'13). IEEE Computer Society, 255--265.

[64]

Michael Viderman. 2015. A combination of testability and decodability by tensor products. Random Struct. Algor. 46, 3 (2015), 572--598.

Digital Library

[65]

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’05). Springer, 1424--1436.

Digital Library

[66]

David P. Woodruff. 2007. New lower bounds for general locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC) 14, 006 (2007).

[67]

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

Digital Library

[68]

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

Digital Library

[69]

Victor V. Zyablov. 1971. An estimate on the complexity of constructing binary linear cascade codes. Probl. Inf. Trans. 7, 1 (1971), 3--10.

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
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
Block ABlocki JCheng KGrigorescu ELi XZheng YZhu M(2023)On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion ErrorsProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.14(1-25)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.14
Show More Cited By

Index Terms

High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Error-correcting codes

Recommendations

High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity
STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing

In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist LCCs and LTCs with block ...
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 ...
Linear-time encodable/decodable codes with near-optimal rate

We present an explicit construction of linear-time encodable and decodable codes of rate r which can correct a fraction (1-r-ε)/2 of errors over an alphabet of constant size depending only on ε, for every 0 0. The error-correction performance of these ...

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 64, Issue 2

April 2017

277 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3080497

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2017 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 May 2017

Accepted: 01 February 2017

Revised: 01 January 2017

Received: 01 May 2016

Published in JACM Volume 64, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

NSF
Sloan Fellowship, Rothschild Fellowship
ERC
Israel Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
446
Total Downloads

Downloads (Last 12 months)98
Downloads (Last 6 weeks)13

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
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
Block ABlocki JCheng KGrigorescu ELi XZheng YZhu M(2023)On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion ErrorsProceedings of the conference on Proceedings of the 38th Computational Complexity Conference10.4230/LIPIcs.CCC.2023.14(1-25)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2023.14
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
Block ABlocki J(2023)Computationally Relaxed Locally Decodable Codes, Revisited2023 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT54713.2023.10206655(2714-2719)Online publication date: 25-Jun-2023
https://doi.org/10.1109/ISIT54713.2023.10206655
Doron DMoshkovitz DOh JZuckerman D(2022)Nearly Optimal Pseudorandomness from HardnessJournal of the ACM10.1145/355530769:6(1-55)Online publication date: 17-Nov-2022
https://dl.acm.org/doi/10.1145/3555307
Dinur IEvra SLivne RLubotzky AMozes SLeonardi SGupta A(2022)Locally testable codes with constant rate, distance, and localityProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520024(357-374)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520024
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
Ameri MBlock ABlocki J(2022)Memory-Hard Puzzles in the Standard Model with Applications to Memory-Hard Functions and Resource-Bounded Locally Decodable CodesSecurity and Cryptography for Networks10.1007/978-3-031-14791-3_3(45-68)Online publication date: 5-Sep-2022
https://doi.org/10.1007/978-3-031-14791-3_3
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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents