research-article

Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length

Authors:

Andrew MillsAuthors Info & Claims

ACM Transactions on Computation Theory (TOCT), Volume 3, Issue 2

Article No.: 5, Pages 1 - 34

https://doi.org/10.1145/2077336.2077338

Published: 01 January 2012 Publication History

Abstract

Locally decodable codes are error-correcting codes with the extra property that, in order to retrieve the value of a single input position, it is sufficient to read a small number of positions of the codeword. We refer to the probability of getting the correct value as the correctness of the decoding algorithm.

A breakthrough result by Yekhanin [2007] showed that 3-query linear locally decodable codes may have subexponential length. The construction of Yekhanin, and the three query constructions that followed, achieve correctness only up to a certain limit which is 1 − 3δ for nonbinary codes, where an adversary is allowed to corrupt up to δ fraction of the codeword. The largest correctness for a subexponential length 3-query binary code is achieved in a construction by Woodruff [2008], and it is below 1 − 3δ.

We show that achieving slightly larger correctness (as a function of δ) requires exponential codeword length for 3-query codes. Previously, there were no larger than quadratic lower bounds known for locally decodable codes with more than 2 queries, even in the case of 3-query linear codes. Our lower bounds hold for linear codes over arbitrary finite fields and for binary nonlinear codes. Considering larger number of queries, we obtain lower bounds for q-query codes for q > 3, under certain assumptions on the decoding algorithm that have been commonly used in previous constructions. We also prove bounds on the largest correctness achievable by these decoding algorithms, regardless of the length of the code. Our results explain the limitations on correctness in previous constructions using such decoding algorithms. In addition, our results imply trade-offs on the parameters of error-correcting data structures.

References

[1]

Alon, N., Babai, L., and Itai, A. 1986. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algor. 7, 567--583.

Digital Library

[2]

Babai, L., Fortnow, L., Levin, L. A., and Szegedy, M. 1991. Checking computations in polylogarithmic time. In Proceedings of the ACM Symposium on Theory of Computing (STOC’91). 21--32.

Digital Library

[3]

Beaver, D. and Feigenbaum, J. 1990. Hiding instances in multioracle queries. In Proceedings of the Symposium on Theoritical Aspects of Computer Science (STACS’90). 37--48.

Digital Library

[4]

Ben-Aroya, A., Regev, O., and Wolf, R. d. 2008. A hypercontractive inequality for matrix-valued functions with applications to quantum computing and ldcs. In Proceedings of the IEEE Annual Symposium on Foundations of Computer Science (FOCS’08). 477--486.

Digital Library

[5]

Ben-Aroya, A., Efremenko, K., and Ta-Shma, A. 2010. Local list decoding with a constant number of queries. In Proceedings of the IEEE Annual Symposium on Foundations of Computer Science (FOCS’10). 715--722.

Digital Library

[6]

de Wolf, R. 2009. Error-correcting data structures. In Proceedings of the Symposium on Theoritical Aspects of Computer Science (STACS’09). 313--324.

[7]

Deshpande, A., Jain, R., Kavitha, T., Radhakrishnan, J., and Lokam, S. V. 2005. Lower bounds for adaptive locally decodable codes. Random Struct. Algor. 27, 3, 358--378.

Digital Library

[8]

Dvir, Z. 2010. On matrix rigidity and locally self-correctable codes. In Proceedings of the IEEE Conference on Computational Complexity. 291--298.

Digital Library

[9]

Dvir, Z. and Shpilka, A. 2005. Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. In Proceedings of the ACM Symposium on Theory of Computing (STOC’05). 592--601.

Digital Library

[10]

Dvir, Z., Gopalan, P., and Yekhanin, S. 2010. Matching vector codes. In Proceedings of the IEEE Annual Symposium on Foundations of Computer Science (FOCS’10). 705--714.

Digital Library

[11]

Efremenko, K. 2009. 3-query locally decodable codes of subexponential length. In Proceedings of the ACM Symposium on Theory of Computing (STOC’09). 39--44.

Digital Library

[12]

Gal, A. and Mills, A. 2011. Three query linear locally decodable codes with higher correctness require exponential length. In Proceedings of the Symposium on Theoritical Aspects of Computer Science (STACS’11). 673--684.

[13]

Goldreich, O., Karloff, H., Schulman, L. J., and Trevisan, L. 2006. Lower bounds for linear locally decodable codes and private information retrieval. Comput. Complex. 15, 3, 263--296.

Digital Library

[14]

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

Digital Library

[15]

Kerenidis, I. and de Wolf, R. 2003. Exponential lower bound for 2-query locally decodable codes via a quantum argument. In Proceedings of the ACM Symposium on Theory of Computing (STOC’03). 106--115.

Digital Library

[16]

Kopparty, S., Saraf, S., and Yekhanin, S. 2011. High-rate codes with sublinear-time decoding. In Proceedings of the ACM Symposium on Theory of Computing (STOC’11). 167--176.

Digital Library

[17]

Miltersen, P. B. 1999. Cell probe complexity - a survey. In Advances in Data Structures Workshop.

[18]

Obata, K. 2002. Optimal lower bounds for 2-query locally decodable linear codes. In Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX-RANDOM’02). 39--50.

Digital Library

[19]

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

[20]

Shiowattana, D. and Lokam, S. V. 2006. An optimal lower bound for 2-query locally decodable linear codes. Inf. Process. Lett. 97, 6, 244--250.

Digital Library

[21]

Sudan, M., Trevisan, L., and Vadhan, S. 1999. Pseudorandom generators without the xor lemma. In Proceedings of the ACM Symposium on Theory of Computing (STOC’99). 537--546.

Digital Library

[22]

Trevisan, L. 2004. Some applications of coding theory in computational complexity. In Proceedings of the Electronic Colloquium on Computational Complexity (ECCC TR04-043).

[23]

Wehner, S. and de Wolf, R. 2005. Improved lower bounds for locally decodable codes and private information retrieval. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP’05). 1424--1436.

Digital Library

[24]

Woodruff, D. 2006. Some new lower bounds for general locally decodable codes. In Proceedings of the Electronic Colloquium on Computational Complexity (ECCC TR07-006).

[25]

Woodruff, D. 2008. Corruption and recovery-efficient locally decodable codes. In Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX-RANDOM’08). 584--595.

Digital Library

[26]

Woodruff, D. 2010. A quadratic lower bound for three-query linear locally decodable codes over any field. In Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX-RANDOM’10). 766--779.

Digital Library

[27]

Yekhanin, S. 2007. Towards 3-query locally decodable codes of subexponential length. In Proceedings of the ACM Symposium on Theory of Computing (STOC’07). 266--274.

Digital Library

Cited By

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
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
Paradise O(2021)Smooth and Strong PCPscomputational complexity10.1007/s00037-020-00199-330:1Online publication date: 6-Jan-2021
https://doi.org/10.1007/s00037-020-00199-3
Show More Cited By

Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length
1. Theory of computation

Recommendations

3-query locally decodable codes of subexponential length
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

Locally Decodable Codes (LDC) allow one to decode any particular symbol of the input message by making a constant number of queries to a codeword, even if a constant fraction of the codeword is damaged. In a recent work [Yek08] Yekhanin constructs a 3-...
3-Query Locally Decodable Codes of Subexponential Length
^† Special Section on the Forty-First Annual ACM Symposium on Theory of Computing (STOC 2009)

Locally decodable codes (LDCs) allow one to decode any particular symbol of the input message by making a constant number of queries to a codeword, even if a constant fraction of the codeword is damaged. In a recent work [J. ACM, 55 (2008), article 1], ...
Towards 3-query locally decodable codes of subexponential length
STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

A q-query Locally Decodable Code (LDC) encodes an n-bitmessage x as an n-bit codeword C(x), such that one canprobabilistically recover any bit x_i of the message by queryingonly q bits of the codeword C(x), even after some constantfraction of codeword ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computation Theory

ACM Transactions on Computation Theory Volume 3, Issue 2

January 2012

99 pages

ISSN:1942-3454

EISSN:1942-3462

DOI:10.1145/2077336

Issue’s Table of Contents

Copyright © 2012 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: 01 January 2012

Accepted: 01 November 2011

Revised: 01 September 2011

Received: 01 January 2011

Published in TOCT Volume 3, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Division of Computing and Communication Foundations

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
208
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

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
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
Paradise O(2021)Smooth and Strong PCPscomputational complexity10.1007/s00037-020-00199-330:1Online publication date: 6-Jan-2021
https://doi.org/10.1007/s00037-020-00199-3
Sun HJafar S(2020)On the Capacity of Locally Decodable CodesIEEE Transactions on Information Theory10.1109/TIT.2020.301497366:10(6566-6579)Online publication date: Oct-2020
https://doi.org/10.1109/TIT.2020.3014973
Azaria ARichardson AKraus SCosley DForte ACiolfi LMcDonald D(2015)An Agent for Deception Detection in Discussion Based EnvironmentsProceedings of the 18th ACM Conference on Computer Supported Cooperative Work & Social Computing10.1145/2675133.2675137(218-227)Online publication date: 28-Feb-2015
https://dl.acm.org/doi/10.1145/2675133.2675137
Lalitha VPrakash NKamath GKumar P(2012)On t-designs and bounds relating query complexity to error resilience in locally correctable codes2012 National Conference on Communications (NCC)10.1109/NCC.2012.6176752(1-5)Online publication date: Feb-2012
https://doi.org/10.1109/NCC.2012.6176752
Woodruff D(2012)A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any FieldJournal of Computer Science and Technology10.1007/s11390-012-1254-827:4(678-686)Online publication date: 12-Jul-2012
https://doi.org/10.1007/s11390-012-1254-8

View Options

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.

Figures

Tables

Media

View Issue’s Table of Contents