research-article

A new family of locally correctable codes based on degree-lifted algebraic geometry codes

Authors:

Eli Ben-Sasson,

Swastik Kopparty,

Shubangi SarafAuthors Info & Claims

STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

Pages 833 - 842

https://doi.org/10.1145/2488608.2488714

Published: 01 June 2013 Publication History

Abstract

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, univariate polynomials evaluated over the q-element field (also known as Reed-Solomon codes) are "lifted" to degree-d, m-variate polynomials (Reed-Muller codes). A number of properties are established: The rate of the degree-lifted code is approximately a 1/m!-fraction of the rate of the base-code. The relative distance of the degree-lifted code is at least as large as that of the base-code. This is proved using a generalization of the Schwartz-Zippel Lemma to degree-lifted Algebraic-Geometry codes. [Local correction] If the base code is invariant under a group that is "close" to being doubly-transitive (in a precise manner defined later then the degree-lifted code is locally correctable with query complexity at most q². The automorphisms of the base-code are crucially used to generate query-sets, abstracting the use of affine-lines in the local correction procedure of Reed-Muller codes. Taking a concrete illustrating example, we show that degree-lifted Hermitian codes form a family of locally correctable codes over an alphabet that is significantly smaller than that obtained by Reed-Muller codes of similar constant rate, message length, and distance.

References

[1]

N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron. Testing Reed-Muller codes. IEEE Transactions on Information Theory, 51(11):4032--4039, 2005.

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, Jan. 1998.

Digital Library

[3]

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

[4]

L. Babai, L. Fortnow, L. A. Levin, and M. Szegedy. Checking computations in polylogarithmic time. In STOC '91: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 21--32, New York, NY, USA, 1991. ACM.

Digital Library

[5]

L. Babai, L. Fortnow, and C. Lund. Addendum to non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 2:374, 1992.

Digital Library

[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]

L. Babai, A. Shpilka, and D. Stefankovic. Locally testable cyclic codes. In IEEE, editor, Proceedings: 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003, 11--14 October 2003, Cambridge, Massachusetts, pages 116--125, pub-IEEE:adr, 2003. IEEE Computer Society Press.

Digital Library

[8]

D. Beaver and J. Feigenbaum. Hiding instances in multioracle queries. In Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science, STACS '90, pages 37--48. 1990.

Digital Library

[9]

A. Ben-Aroya, K. Efremenko, and A. Ta-Shma. Local list decoding with a constant number of queries. Electronic Colloquium on Computational Complexity (ECCC), 17:47, 2010.

[10]

A. Ben-Aroya and A. Ta-Shma. Constructing small-bias sets from algebraic-geometric codes. In FOCS, pages 191--197. IEEE Computer Society, 2009.

Digital Library

[11]

E. Ben-Sasson, E. Grigorescu, G. Maatouk, A. Shpilka, and M. Sudan. On sums of locally testable affine invariant properties. Electronic Colloquium on Computational Complexity (ECCC), 18:79, 2011.

[12]

E. Ben-Sasson, V. Guruswami, T. Kaufman, M. Sudan, and M. Viderman. Locally testable codes require redundant testers. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC), pages 52--61, 2009.

Digital Library

[13]

E. Ben-Sasson, P. Harsha, and S. Raskhodnikova. Some 3CNF properties are hard to test. SIAM J. on Computing, 35(1):1--21, 2005.

Digital Library

[14]

E. Ben-Sasson, G. Maatouk, A. Shpilka, and M. Sudan. Symmetric LDPC codes are not necessarily locally testable. In preparation, 2010.

[15]

E. Ben-Sasson, N. Ron-Zewi, and M. Sudan. Sparse affine-invariant linear codes are locally testable. Electronic Colloquium on Computational Complexity (ECCC), 19:49, 2012.

[16]

E. Ben-Sasson and M. Sudan. Simple PCPs with poly-log rate and query complexity. In H. N. Gabow and R. Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22--24, 2005, pages 266--275. ACM, 2005.

Digital Library

[17]

E. Ben-Sasson and M. Sudan. Limits on the rate of locally testable affine-invariant codes. Electronic Colloquium on Computational Complexity (ECCC), 17:108, 2010.

[18]

E. Ben-Sasson and M. Viderman. Composition of Semi-LTCs by Two-Wise Tensor Products. In Proceedings of the Approximation, Randomization, and Combinatorial Optimization, (APPROX-RANDOM 2009), volume 5687 of Lecture Notes in Computer Science, pages 378--391. Springer, 2009.

Digital Library

[19]

E. Ben-Sasson and M. Viderman. Tensor Products of Weakly Smooth Codes are Robust. Theory of Computing, 5(1):239--255, 2009.

[20]

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

[21]

B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. Journal of the ACM, 45:965--981, 1998.

Digital Library

[22]

D. Coppersmith and A. Rudra. On the Robust Testability of Product of Codes. Electronic Colloquium on Computational Complexity (ECCC), (104), 2005.

[23]

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

Digital Library

[24]

I. Dinur, M. Sudan, and A. Wigderson. Robust local testability of tensor products of LDPC codes. In J. Díaz, K. Jansen, J. D. P. Rolim, and U. Zwick, editors, APPROX-RANDOM, volume 4110 of Lecture Notes in Computer Science, pages 304--315. Springer, 2006.

Digital Library

[25]

Z. Dvir, P. Gopalan, and S. Yekhanin. Matching vector codes. Electronic Colloquium on Computational Complexity (ECCC), 17:12, 2010.

[26]

K. Efremenko. 3-query locally decodable codes of subexponential length. In M. Mitzenmacher, editor, STOC, pages 39--44. ACM, 2009.

Digital Library

[27]

K. Efremenko. From irreducible representations to locally decodable codes. In STOC, pages 327--338, 2012.

Digital Library

[28]

L. Fortnow and S. P. Vadhan, editors. Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6--8 June 2011. ACM, 2011.

[29]

K. Friedl and M. Sudan. Some improvements to total degree tests. In ISTCS, pages 190--198, 1995.

Digital Library

[30]

A. Garcia and H. Stichtenoth. On the Asymptotic Behaviour of Some Towers of Function Fields over Finite Fields. Journal of Number Theory, 61:248--273, 1996.

[31]

O. Goldreich, H. J. Karloff, L. J. Schulman, and L. Trevisan. Lower bounds for linear locally decodable codes and private information retrieval. In IEEE Conference on Computational Complexity, pages 175--183, 2002.

Digital Library

[32]

V. Goppa. Algebraic-geometric codes. Izu. Akad. Nauk SSSR Ser. Mat, 46(4):762--781, 1982.

[33]

V. D. Goppa. Geometry and Codes. Springer, 1988.

[34]

E. Grigorescu, T. Kaufman, and M. Sudan. Succinct representation of codes with applications to testing. In I. Dinur, K. Jansen, J. Naor, and J. D. P. Rolim, editors, APPROX-RANDOM, volume 5687 of Lecture Notes in Computer Science, pages 534--547. Springer, 2009.

Digital Library

[35]

A. Guo, S. Kopparty, and M. Sudan. New affine-invariant codes from lifting. In ITCS, pages 529--540, 2013.

Digital Library

[36]

R. W. Hamming. Error detecting and error correcing codes. Bell System Technical Journal, 29:147---160, 1950.

[37]

J. P. Hansen and H. Stichtenoth. Group codes on certain algebraic curves with many rational points. Appl. Algebra Eng. Commun. Comput., 1:67--77, 1990.

Digital Library

[38]

S. Hansen. Error-correcting codes from higher-dimensional varieties. Finite Fields Appl., 7:530--552, 2001.

Digital Library

[39]

R. Impagliazzo and A. Wigderson. P = BPP if e requires exponential circuits: Derandomizing the xor lemma. In F. T. Leighton and P. W. Shor, editors, STOC, pages 220--229. ACM, 1997.

Digital Library

[40]

T. Itoh and Y. Suzuki. Improved constructions for query-efficient locally decodable codes of subexponential length. IEICE Transactions, 93-D(2):263--270, 2010.

[41]

J. Katz and L. Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, STOC '00, pages 80--86, New York, NY, USA, 2000. ACM.

Digital Library

[42]

T. Kaufman and A. Lubotzky. Edge transitive ramanujan graphs and symmetric ldpc good codes. In H. J. Karloff and T. Pitassi, editors, STOC, pages 359--366. ACM, 2012.

Digital Library

[43]

T. Kaufman and M. Sudan. Algebraic property testing: the role of invariance. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pages 403--412, 2008.

Digital Library

[44]

T. Kaufman and M. Viderman. Locally testable vs. locally decodable codes. In M. J. Serna, R. Shaltiel, K. Jansen, and J. D. P. Rolim, editors, APPROX-RANDOM, volume 6302 of Lecture Notes in Computer Science, pages 670--682. Springer, 2010.

Digital Library

[45]

T. Kaufman and A. Wigderson. Symmetric ldpc codes and local testing. In A. C.-C. Yao, editor, ICS, pages 406--421. Tsinghua University Press, 2010.

[46]

I. Kerenidis and R. de Wolf. Exponential lower bound for 2-query locally decodable codes via a quantum argument. J. Comput. Syst. Sci., 69(3):395--420, 2004.

Digital Library

[47]

S. Kopparty, S. Saraf, and S. Yekhanin. High-rate codes with sublinear-time decoding. In Fortnow and Vadhancite DBLP: conf/stoc/2011, pages 167--176.

Digital Library

[48]

J. L. L. Gold and H. Schenck. Cayley-bacharach and evaluation codes on complete intersections. J. Pure Appl. Algebra, 196:91--99, 2005.

[49]

G. Lachaud. Number of points of plane sections and linear codes defined on algebraic varieties. Arithmetic, Geometry and Coding Theory, Proceedings Luminy, pages 77--104, 1993.

[50]

R. J. Lipton. Efficient checking of computations. In Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science, STACS '90, pages 207--215, 1990.

Digital Library

[51]

J. B. Little. Algebraic geometry codes from higher dimensional varieties. CoRR, abs/0802.2349, 2008.

[52]

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

Digital Library

[53]

S. V. M.A. Tsfasman and T. Zink. Modular curves, shimura curves, and goppa codes, better than varshamov-gilbert bound. math. Nachr., 109:21--28, 1982.

[54]

F. J. MacWilliams and N. J. A. Sloane. The theory of error-correcting codes. North-Holland Amsterdam, 1978.

[55]

K. Obata. Optimal lower bounds for 2-query locally decodable linear codes. In J. D. P. Rolim and S. P. Vadhan, editors, RANDOM, volume 2483 of Lecture Notes in Computer Science, pages 39--50. Springer, 2002.

Digital Library

[56]

J. Pedersen. A function field related to the ree group. Lect. Notes Math., 1518:122--132, 1992.

[57]

P. Raghavendra. A note on yekhanin's locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC), 14(016), 2007.

[58]

A. A. Razborov and S. Yekhanin. An omega(n1/3) lower bound for bilinear group based private information retrieval. Theory of Computing, 3(1):221--238, 2007.

[59]

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

[60]

F. rodier. Codes from flag varieties over a finite field. J. Pure Appl. Algebra, 178:203--214, 2003.

[61]

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

[62]

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

Digital Library

[63]

C. E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27:379---423, 623--656, 1948.

[64]

C. E. Shannon. Communication theory - exposition of fundamentals. IEEE Transactions on Information Theory, 1:44--47, 1953.

[65]

H. Stichtenoth. On automorphisms of geometric goppa codes. Journal of Algebra, page 113.

[66]

H. Stichtenoth. Algebraic function fields and codes. Universitext. Springer, 1993.

[67]

M. Sudan. Invariance in property testing. Electronic Colloquium on Computational Complexity (ECCC), (051), 2010.

[68]

M. Sudan, L. Trevisan, and S. P. Vadhan. Pseudorandom generators without the xor lemma (extended abstract). In J. S. Vitter, L. L. Larmore, and F. T. Leighton, editors, STOC, pages 537--546. ACM, 1999.

Digital Library

[69]

M. Tsfasman and S.G.Vladut. Algebraic-geometric codes. (Kluwer, Dordrecht, 1991.

Digital Library

[70]

P. Valiant. The tensor product of two codes is not necessarily robustly testable. In C. Chekuri, K. Jansen, J. D. P. Rolim, and L. Trevisan, editors, APPROX-RANDOM, volume 3624 of Lecture Notes in Computer Science, pages 472--481. Springer, 2005.

Digital Library

[71]

S. Wehner and R. de Wolf. Improved lower bounds for locally decodable codes and private information retrieval. In L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi, and M. Yung, editors, ICALP, volume 3580 of Lecture Notes in Computer Science, pages 1424--1436. Springer, 2005.

Digital Library

[72]

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

[73]

C. Xing. On automorphism groups of the hermitian codes. IEEE Transactions on Information Theory, 41(6):1629--1635, 1995.

[74]

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

Digital Library

[75]

S. Yekhanin. Locally decodable codes: A brief survey. In Y. M. Chee, Z. Guo, S. Ling, F. Shao, Y. Tang, H. Wang, and C. Xing, editors, IWCC, volume 6639 of Lecture Notes in Computer Science, pages 273--282. Springer, 2011.

Digital Library

Cited By

Matthews GMurphy A(2022)Norm-trace-lifted codes over binary fields2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834497(3079-3084)Online publication date: 26-Jun-2022
https://doi.org/10.1109/ISIT50566.2022.9834497
Cramer RXing CYuan C(2020)Efficient Multi-Point Local Decoding of Reed-Muller Codes via Interleaved CodexIEEE Transactions on Information Theory10.1109/TIT.2019.293913566:1(263-272)Online publication date: Jan-2020
https://doi.org/10.1109/TIT.2019.2939135
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
Show More Cited By

Index Terms

A new family of locally correctable codes based on degree-lifted algebraic geometry codes
1. Software and its engineering
  1. Software creation and management
    1. Software development techniques
      1. Error handling and recovery

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 ...
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 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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

June 2013

998 pages

ISBN:9781450320290

DOI:10.1145/2488608

General Chairs:
Dan Boneh
Stanford University, USA
,
Tim Roughgarden
Stanford University, USA
,
Program Chair:
Joan Feigenbaum
Yale University, USA

Copyright © 2013 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: 01 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'13

Sponsor:

SIGACT

STOC'13: Symposium on Theory of Computing

June 1 - 4, 2013

California, Palo Alto, USA

Acceptance Rates

STOC '13 Paper Acceptance Rate 100 of 360 submissions, 28%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
208
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Matthews GMurphy A(2022)Norm-trace-lifted codes over binary fields2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834497(3079-3084)Online publication date: 26-Jun-2022
https://doi.org/10.1109/ISIT50566.2022.9834497
Cramer RXing CYuan C(2020)Efficient Multi-Point Local Decoding of Reed-Muller Codes via Interleaved CodexIEEE Transactions on Information Theory10.1109/TIT.2019.293913566:1(263-272)Online publication date: Jan-2020
https://doi.org/10.1109/TIT.2019.2939135
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
Ben-Sasson EKaplan YKopparty SMeir OStichtenoth H(2013)Constant Rate PCPs for Circuit-SAT with Sublinear Query ComplexityProceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science10.1109/FOCS.2013.42(320-329)Online publication date: 26-Oct-2013
https://dl.acm.org/doi/10.1109/FOCS.2013.42

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents