More Web Proxy on the site http://driver.im/

research-article

Locally testable codes with constant rate, distance, and locality

Authors:

Alexander Lubotzky,

Shahar MozesAuthors Info & Claims

STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

Pages 357 - 374

https://doi.org/10.1145/3519935.3520024

Published: 10 June 2022 Publication History

Abstract

A locally testable code (LTC) is an error correcting code that has a property-tester. The tester reads q bits that are randomly chosen, and rejects words with probability proportional to their distance from the code. The parameter q is called the locality of the tester.

LTCs were initially studied as important components of probabilistically checkable proofs (PCP), and since then the topic has evolved on its own. High rate LTCs could be useful in practice: before attempting to decode a received word, one can save time by first quickly testing if it is close to the code.

An outstanding open question has been whether there exist “c³-LTCs”, namely LTCs with constant rate, constant distance, and constant locality.

In this work we construct such codes based on a new two-dimensional complex which we call a left-right Cayley complex. This is essentially a graph which, in addition to vertices and edges, also has squares. Our codes can be viewed as a two-dimensional version of (the one-dimensional) expander codes, where the codewords are functions on the squares rather than on the edges.

References

[1]

Noga Alon and Fan RK Chung. 1988. Explicit construction of linear sized tolerant networks. Discrete Mathematics, 72, 1-3 (1988), 15–19.

Digital Library

[2]

Noga Alon, Jeff Edmonds, and Michael Luby. 1995. Linear time erasure codes with nearly optimal recovery. In Proceedings of IEEE 36th Annual Foundations of Computer Science. 512–519.

[3]

Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. 2019. Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 1–12.

Digital Library

[4]

Sanjeev Arora. 1994. Probabilistic checking of proofs and the hardness of approximation problems. Ph.D. Dissertation. U.C. Berkeley. Available via anonymous ftp as Princeton TR94-476.

[5]

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

[6]

Sanjeev Arora and Shmuel Safra. 1998. Probabilistic Checking of Proofs: A New Characterization of NP. J. ACM, 45, 1 (1998), 70–122.

Digital Library

[7]

László Babai, Lance Fortnow, Leonid Levin, and Mario Szegedy. 1991. Checking Computations in Polylogarithmic Time. In Proc. 23rd ACM Symp. on Theory of Computing. 21–31.

Digital Library

[8]

László Babai, Lance Fortnow, and Carsten Lund. 1991. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1 (1991), 3–40.

[9]

László Babai, Amir Shpilka, and Daniel Stefankovic. 2005. Locally testable cyclic codes. IEEE Trans. Inf. Theory, 51, 8 (2005), 2849–2858. https://doi.org/10.1109/TIT.2005.851735

Digital Library

[10]

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil Vadhan. 2006. Robust PCPs of Proximity, Shorter PCPs and Applications to Coding. SIAM J. Comput., 36, 4 (2006), 889–974. In special issue on Randomness and Computation.

Digital Library

[11]

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, and Michael Viderman. 2010. Locally Testable Codes Require Redundant Testers. SIAM J. Comput., 39, 7 (2010), 3230–3247.

Digital Library

[12]

Eli Ben-Sasson, Prahladh Harsha, and Sofya Raskhodnikova. 2005. Some 3CNF Properties Are Hard to Test. SIAM J. Comput., 35, 1 (2005), 1–21.

Digital Library

[13]

Eli Ben-Sasson and Madhu Sudan. 2005. Simple PCPs with poly-log rate and query complexity. In Proc. 37th ACM Symp. on Theory of Computing. 266–275.

Digital Library

[14]

Eli Ben-Sasson and Madhu Sudan. 2006. Robust locally testable codes and products of codes. Random Structures & Algorithms, 28, 4 (2006), 387–402. https://doi.org/10.1002/rsa.20120 arxiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.20120.

[15]

Eli Ben-Sasson and Madhu Sudan. 2008. Short PCPs with Polylog Query Complexity. SIAM J. Comput., 38, 2 (2008), 551–607. https://doi.org/10.1137/050646445

Digital Library

[16]

Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, and Avi Wigderson. 2003. Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. In Proc. 35th ACM Symp. on Theory of Computing. 612–621.

Digital Library

[17]

Eli Ben-Sasson and Michael Viderman. 2009. Tensor Products of Weakly Smooth Codes are Robust. Theory of Computing, 5, 12 (2009), 239–255. http://www.theoryofcomputing.org/articles/v005a012

[18]

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

[19]

Manuel Blum, Michael Luby, and Ronitt Rubinfeld. 1990. Self-testing/correcting with applications to numerical problems. In Proc. 22nd ACM Symp. on Theory of Computing. 73–83.

Digital Library

[20]

Nikolas P. Breuckmann and Jens N. Eberhardt. 2021. Balanced Product Quantum Codes. IEEE Transactions on Information Theory, 67, 10 (2021), 6653–6674. https://doi.org/10.1109/TIT.2021.3097347

Digital Library

[21]

Donald I. Cartwright and Tim Steger. 1998. A family of ~ A_n-groups. Israel J. Math., 103, 1 (1998), 125–140.

[22]

Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha. 2018. Boolean Function Analysis on High-Dimensional Expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA (LIPIcs, Vol. 116). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 38:1–38:20. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.38

[23]

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

Digital Library

[24]

Irit Dinur. 2021. Breakthroughs in computer science: Locally Testable Codes with Constant Rate, Distance, and Locality. https://simons.berkeley.edu/events/breakthroughs-locally-testable-codes-constant-rate-distance-and-locality.

[25]

Irit Dinur. 2021. Locally Testable Codes with Constant Rate, Distance, and Locality. Part I: https://youtu.be/pz2-bEopa-c, Part II: https://youtu.be/Ydb2OPQ7eqI.

[26]

Irit Dinur and Prahladh Harsha. 2009. Composition of low-error 2-query PCPs using decodable PCPs. In Proc. 50th IEEE Symp. on Foundations of Computer Science.

Digital Library

[27]

Irit Dinur and Tali Kaufman. 2011. Dense Locally Testable Codes Cannot Have Constant Rate and Distance. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings. 507–518.

[28]

Irit Dinur and Tali Kaufman. 2017. Agreement Expansion. Work in progress.

[29]

Irit Dinur, Madhu Sudan, and Avi Wigderson. 2006. Robust local testability of tensor products of LDPC codes. In Proc. 10th International Workshop on Randomization and Computation (RANDOM).

Digital Library

[30]

Shai Evra and Tali Kaufman. 2016. Bounded degree cosystolic expanders of every dimension. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016. 36–48.

Digital Library

[31]

Katalin Friedl and Madhu Sudan. 2013. Some Improvements to Total Degree Tests. CoRR, abs/1307.3975 (2013), arxiv:1307.3975

[32]

Robert G. Gallager. 1963. Low density parity check codes. MIT Press, Cambridge, Massachusetts.

[33]

Howard Garland. 1973. p-Adic Curvature and the Cohomology of Discrete Subgroups of p-Adic Groups. Annals of Mathematics, 97 (1973), 375.

[34]

Edgar N Gilbert. 1952. A comparison of signalling alphabets. The Bell system technical journal, 31, 3 (1952), 504–522.

[35]

Oded Goldreich. 2005. Short Locally Testable Codes and Proofs (survey). ECCC Technical Report TR05-014.

[36]

Oded Goldreich. 2010. Springer Berlin Heidelberg, Berlin, Heidelberg. 65–104.

[37]

Oded Goldreich. 2017. Introduction to Property Testing. Cambridge University Press.

[38]

Oded Goldreich and Or Meir. 2012. The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable. Inform. Process. Lett., 112, 8-9 (2012), https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-062/index.html

Digital Library

[39]

Oded Goldreich and Madhu Sudan. 2006. Locally Testable Codes and PCPs of Almost-Linear Length. J. of the ACM, 53, 4 (2006), 558–655.

Digital Library

[40]

Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, and Shubhangi Saraf. 2018. Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov Bound. IEEE Trans. Inf. Theory, 64, 8 (2018), 5813–5831. https://doi.org/10.1109/TIT.2018.2809788

Digital Library

[41]

Bruce Jordan and Ron Livne. 1999. The Ramanujan property for regular cubical complexes. Duke Mathematical Journal, 105 (1999), 85–103.

[42]

Tali Kaufman, David Kazhdan, and Alexander Lubotzky. 2014. Ramanujan Complexes and Bounded Degree Topological Expanders. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014. 484–493.

[43]

Tali Kaufman and Alexander Lubotzky. 2012. Edge transitive Ramanujan graphs and symmetric LDPC good codes. In Proceedings of the 44 th symposium on Theory of Computing. 359–366.

Digital Library

[44]

Tali Kaufman and Alexander Lubotzky. 2014. High dimensional expanders and property testing. In Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12-14, 2014. 501–506. https://doi.org/10.1145/2554797.2554842

Digital Library

[45]

Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. 2017. High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity. J. ACM, 64, 2 (2017), 11:1–11:42. https://doi.org/10.1145/3051093

Digital Library

[46]

Aleksandr Gennadievich Kurosh. 1955. The Theory of Groups, vol. 2. Chelsea publishing company, New York.

[47]

Alexander Lubotzky. 1994. Discrete groups, expanding graphs and invariant measures. Birkhäuser Verlag, Basel. https://doi.org/10.1007/978-3-0346-0332-4 With an appendix by Jonathan D. Rogawski.

[48]

Alexander Lubotzky. 2021. The C^3 Problem: Locally Testable Codes with Constant Rate and Constant Distance. https://www.simonsfoundation.org/event/2021-mps-conference-on-high-dimensional-expanders/ MPS Conference on High-Dimensional Expanders.

[49]

Alexander Lubotzky and Roy Meshulam. 2007. A Moore bound for simplicial complexes. Bulletin of the London Mathematical Society, 39, 3 (2007), 353–358.

[50]

Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. 1988. Ramanujan Graphs. Combinatorica, 8 (1988), 261–277.

[51]

Alexander Lubotzky, Beth Samuels, and Uzi Vishne. 2005. Explicit constructions of Ramanujan complexes of type ~ A_d. European J. Combin., 26, 6 (2005), 965–993. arxiv:math/0406217. https://dx.doi.org/10.1016/j.ejc.2004.06.007

Digital Library

[52]

Alexander Lubotzky, Beth Samuels, and Uzi Vishne. 2005. Ramanujan complexes of type ~ A_d. Israel J. Math., 149, 1 (2005), 267–299. arxiv:math/0406208. https://dx.doi.org/10.1007/BF02772543

[53]

Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. 1992. Algebraic Methods for Interactive Proof Systems. J. ACM, 39, 4 (1992), October, 859–868.

Digital Library

[54]

Or Meir. 2008. Combinatorial Construction of Locally Testable Codes. In Proc. 40th ACM Symp. on Theory of Computing. 285–294.

Digital Library

[55]

Moshe Morgenstern. 1994. Existence and explicit constructions of q+1 regular Ramanujan graphs for every prime power q. Journal of Combinatorial Theory, Series B, 62, 1 (1994), 44–62.

Digital Library

[56]

Shahar Mozes. 1991. A zero entropy, mixing of all orders tiling system, Symbolic dynamics and its applications. Contemp. Math, 135 (1991), 319–325.

[57]

David Mumford. 1979. An Algebraic Surface with K Ample, (K^2)= 9, p_g = q = 0. American Journal of Mathematics, 101 (1979), 02, isbn:978-1-4419-1936-6 https://doi.org/10.2307/2373947

[58]

Izhar Oppenheim. 2018. Local Spectral Expansion Approach to High Dimensional Expanders Part I: Descent of Spectral Gaps. Discret. Comput. Geom., 59, 2 (2018), 293–330.

Digital Library

[59]

Pavel Panteleev and Gleb Kalachev. 2021. Asymptotically Good Quantum and Locally Testable Classical LDPC Codes. arxiv:2111.03654.

[60]

Pavel Panteleev and Gleb Kalachev. 2021. Quantum LDPC Codes with Almost Linear Minimum Distance. IEEE Transactions on Information Theory, 1–1. https://doi.org/10.1109/TIT.2021.3119384

Digital Library

[61]

Alexander Polishchuk and Dan Spielman. 1994. Nearly Linear Size Holographic Proofs. In Proc. 26th ACM Symp. on Theory of Computing. 194–203.

Digital Library

[62]

Ronitt Rubinfeld and Madhu Sudan. 1996. Robust Characterizations of Polynomials with Applications to Program Testing. SIAM J. Comput., 25, 2 (1996), 252–271.

Digital Library

[63]

Michael Sipser and Daniel A. Spielman. 1996. Expander codes. IEEE Trans. Inform. Theory, 42, 6, part 1 (1996), 1710–1722. coden:IETTAW issn:0018-9448 Codes and complexity.

[64]

Daniel A. Spielman. 1996. Linear-time encodable and decodable error-correcting codes. IEEE Trans. Inform. Theory, 42, 6, part 1 (1996), 1723–1731. coden:IETTAW issn:0018-9448 Codes and complexity.

[65]

R. Michael Tanner. 1981. A Recursive Approach to Low Complexity Codes. IEEE Trans. Inform. Theory, Vol. IT-27, 5 (1981), 533–547.

Digital Library

[66]

Christian Thommesen. 1983. The existence of binary linear concatenated codes with Reed-Solomon outer codes which asymptotically meet the Gilbert-Varshamov bound. IEEE transactions on information theory, 29, 6 (1983), 850–853.

Digital Library

[67]

Paul Valiant. 2005. The Tensor Product of Two Codes Is Not Necessarily Robustly Testable. In APPROX-RANDOM. 472–481.

[68]

Rom Rubenovich Varshamov. 1957. Estimate of the number of signals in error correcting codes. Docklady Akad. Nauk, SSSR, 117 (1957), 739–741.

[69]

Yakov Varshavsky. 1998. p-adic uniformization of unitary Shimura varieties. Publ. Math. IHES, 87, 1 (1998), 57–119.

Cited By

Wills ALin THsieh M(2025)Tradeoff Constructions for Quantum Locally Testable CodesIEEE Transactions on Information Theory10.1109/TIT.2024.350350071:1(426-458)Online publication date: Jan-2025
https://doi.org/10.1109/TIT.2024.3503500
Hong YGuo JLucas A(2025)Quantum memory at nonzero temperature in a thermodynamically trivial systemNature Communications10.1038/s41467-024-55570-716:1Online publication date: 2-Jan-2025
https://doi.org/10.1038/s41467-024-55570-7
Cross AHe ZNatarajan ASzegedy MZhu G(2024)Quantum Locally Testable Code with Constant SoundnessQuantum10.22331/q-2024-10-18-15018(1501)Online publication date: 18-Oct-2024
https://doi.org/10.22331/q-2024-10-18-1501
Show More Cited By

Index Terms

Locally testable codes with constant rate, distance, and locality
1. Mathematics of computing
  1. Information theory

Recommendations

Short locally testable codes and proofs
Studies in complexity and cryptography

We survey known results regarding locally testable codes and locally testable proofs (known as PCPs), with emphasis on the length of these constructs. Local testability refers to approximately testing large objects based on a very small number of probes,...
Local correctability of expander codes

In this work, we present the first local-decoding algorithm for expander codes. This yields a new family of constant-rate codes that can recover from a constant fraction of errors in the codeword symbols, and where any symbol of the codeword can be ...
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 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

June 2022

1698 pages

ISBN:9781450392648

DOI:10.1145/3519935

General Chair:
Stefano Leonardi
Sapienza University of Rome, Italy
,
Program Chair:
Anupam Gupta
Carnegie Mellon University, USA

Copyright © 2022 Owner/Author.

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 June 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '22

Sponsor:

SIGACT

STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing

June 20 - 24, 2022

Rome, Italy

Acceptance Rates

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

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
485
Total Downloads

Downloads (Last 12 months)179
Downloads (Last 6 weeks)16

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wills ALin THsieh M(2025)Tradeoff Constructions for Quantum Locally Testable CodesIEEE Transactions on Information Theory10.1109/TIT.2024.350350071:1(426-458)Online publication date: Jan-2025
https://doi.org/10.1109/TIT.2024.3503500
Hong YGuo JLucas A(2025)Quantum memory at nonzero temperature in a thermodynamically trivial systemNature Communications10.1038/s41467-024-55570-716:1Online publication date: 2-Jan-2025
https://doi.org/10.1038/s41467-024-55570-7
Cross AHe ZNatarajan ASzegedy MZhu G(2024)Quantum Locally Testable Code with Constant SoundnessQuantum10.22331/q-2024-10-18-15018(1501)Online publication date: 18-Oct-2024
https://doi.org/10.22331/q-2024-10-18-1501
Ostrev DOrsucci DLázaro FMatuz B(2024)Classical product code constructions for quantum Calderbank-Shor-Steane codesQuantum10.22331/q-2024-07-22-14208(1420)Online publication date: 22-Jul-2024
https://doi.org/10.22331/q-2024-07-22-1420
Leverrier AZémor G(2024)Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codesACM Transactions on Algorithms10.1145/3663763Online publication date: 7-May-2024
https://dl.acm.org/doi/10.1145/3663763
Ron-Zewi NRothblum R(2024)Local Proofs Approaching the Witness LengthJournal of the ACM10.1145/366148371:3(1-42)Online publication date: 11-Jun-2024
https://dl.acm.org/doi/10.1145/3661483
Gharibian S(2024)Guest Column: The 7 faces of quantum NPACM SIGACT News10.1145/3639528.363953554:4(54-91)Online publication date: 3-Jan-2024
https://dl.acm.org/doi/10.1145/3639528.3639535
Mostad ORosnes ELin H(2024)Generalizing Quantum Tanner Codes2024 IEEE International Symposium on Information Theory Workshops (ISIT-W)10.1109/ISIT-W61686.2024.10591772(1-6)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT-W61686.2024.10591772
Dikstein YHopkins M(2024)Chernoff Bounds and Reverse Hypercontractivity on HDX2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00060(870-919)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00060
Pacenti MVasić B(2024)Quantum Margulis Codes2024 60th Annual Allerton Conference on Communication, Control, and Computing10.1109/Allerton63246.2024.10735283(1-5)Online publication date: 24-Sep-2024
https://doi.org/10.1109/Allerton63246.2024.10735283
Show More Cited By

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