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

research-article

Combinatorial construction of locally testable codes

Author:

Or MeirAuthors Info & Claims

STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

Pages 285 - 294

https://doi.org/10.1145/1374376.1374419

Published: 17 May 2008 Publication History

Abstract

An error correcting code is said to be locally testable if there is a test that checks whether a given string is a codeword, or rather far from the code, by reading only a constant number of symbols of the string. Locally Testable Codes (LTCs) were first systematically studied by Goldreich and Sudan (J. ACM 53(4)) and since then several Constructions of LTCs have been suggested.

While the best known construction of LTCs by Ben-Sasson and Sudan (STOC 2005) and Dinur (J. ACM 54(3)) achieves very efficient parameters, it relies heavily on algebraic tools and on PCP machinery. In this work we present a new and arguably simpler construction of LTCs that is purely combinatorial, does not rely on PCP machinery and matches the parameters of the best known construction. However, unlike the latter construction, our construction is not entirely explicit.

References

[1]

N. Alon, J. Bruck, J. Naor, M. Naor, and R. Roth, Construction of asymptotically good low rate error-correcting codes through pseudo--random graphs, IEEE Transactions on Information Theory 38, 1992, pages 509--516.

Digital Library

[2]

S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof verification and Intractability of Approximation Problems, Journal of ACM, Volume 45(3), 1998, pages 501--555. Preliminary version in FOCS, 1992, pages 14--23.

Digital Library

[3]

S. Arora and S. Safra, Probabilistic Checkable Proofs: A New Characterization of NP, Journal of ACM volume 45(1), 1998, pages 70--122. Preliminary version in FOCS 1992, pages 2--13.

Digital Library

[4]

E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan and S. Vadhan, Robust PCPs of Proximity, Shorter PCPs and Applications to Coding, SIAM Journal of Computing 36(4), 2006, pages 889--974. Preliminary version in STOC 2004, pages 120--134.

Digital Library

[5]

E. Ben-Sasson and M. Sudan, Robust locally testable codes and products of codes, APPROX-RANDOM 2004, pages 286--297.

[6]

E. Ben-Sasson and M. Sudan, Simple PCPs with poly-log rate and query complexity, STOC 2005, pages 266--275. Full version can be obtained from Eli Ben-Sasson's homepage at http://www.cs.technion.ac.il/~eli/.

Digital Library

[7]

D. Coppersmith and A. Rudra, On the robust testability of tensor products of codes, ECCC TR05--104, 2005.

[8]

I. Dinur, The PCP Theorem by gap amplification, Journal of ACM 54(3), 2007. Preliminary version in STOC 2006, pages 241--250.

Digital Library

[9]

I. Dinur and O. Reingold, Assignment testers: Towards combinatorial proofs of the PCP theorem, SIAM Journal of Computing 36(4), 2006, pages 975--1024. Preliminary version in FOCS 2004, pages 155--164.

Digital Library

[10]

I. Dinur, M. Sudan and A. Wigderson, Robust local testability of tensor products of LDPC codes, APPROX-RANDOM 2006, pages 304--315.

Digital Library

[11]

L. Fortnow, J. Rompel and M. Sipser. On the power of multi--prover interactive protocols, In 3rd IEEE Symp. on Structure in Complexity Theory, 1988, pages 156--161. See errata in 5th IEEE Symp. on Structure in Complexity Theory, 1990, pages 318--319.

[12]

O. Goldreich, Short locally testable codes and proofs (Survey), ECCC TR05-014, 2005.

[13]

O. Goldreich and O. Meir, The tensor product of two good codes is not necessarily locally testable, ECCC TR07-062, 2007.

[14]

O. Goldreich and M. Sudan, Locally testable codes and PCPs of almost linear length, Journal of ACM 53(4), 2006, pages 558--655, Preliminary version in FOCS 2002, pages 13--22.

Digital Library

[15]

S. Hoory, N. Linial and A. Wigderson, Expander Graphs and their Applications, Bulletin of AMS, 43(4), 2006, pages 439--561.

[16]

T. Kaufman and M. Sudan, Sparse random linear codes are locally decodable and testable, FOCS 2007.

Digital Library

[17]

O. Meir, Combinatorial construction of locally testable codes, ECCC TR07-115.

[18]

A. Polishchuk and D.A. Spielman, Nearly-linear size holographic proofs, STOC 1994, pages 194--203.

Digital Library

[19]

O. Reingold, S. Vadhan and A. Wigderson, Entropy Waves, the Zig--Zag Graph Product, and New Constant-Degree Expanders and Extractors, FOCS 2000.

Digital Library

[20]

M. Sudan, Algorithmic introduction to coding theory, Lecture notes. Available from http://theory.csail.mit.edu/~madhu/FT01/, 2001.

[21]

P. Valiant, The tensor product of two codes is not necessarily robustly testable, APPROX-RANDOM 2005, pages 472--481.

Digital Library

Cited By

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
Kaufman TWigderson A(2016)Symmetric LDPC codes and local testingCombinatorica10.1007/s00493-014-2715-136:1(91-120)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1007/s00493-014-2715-1
Kaufman TWigderson A(2010)Symmetric LDPC codes and local testingProperty testing10.5555/1986603.1986631(312-319)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1986603.1986631
Show More Cited By

Index Terms

Combinatorial construction of locally testable codes
1. Theory of computation

Recommendations

Strong locally testable codes with relaxed local decoders
CCC '15: Proceedings of the 30th Conference on Computational Complexity

Locally testable codes (LTCs) are error-correcting codes that admit very efficient codeword tests. An LTC is said to be strong if it has a proximity-oblivious tester; that is, a tester that makes only a constant number of queries and reject non-...
Combinatorial Construction of Locally Testable Codes

An error correcting code is said to be locally testable if there is a test that checks whether a given string is a codeword, or rather far from the code, by reading only a constant number of symbols of the string. While the best known construction of ...
Bounds on 2-query Locally Testable Codes with affine tests

We study Locally Testable Codes (LTCs) that can be tested by making two queries to the tested word using an affine test.We show that such LTCs, with high minimal distance, must be of constant size.Our main motivation in studying such LTCs is the Unique ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computing

May 2008

712 pages

ISBN:9781605580470

DOI:10.1145/1374376

General Chair:
Richard Ladner
University of Washington
,
Program Chair:
Cynthia Dwork
Microsoft Research, Silicon Valley

Copyright © 2008 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 May 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '08

Sponsor:

STOC '08: Symposium on Theory of Computing

May 17 - 20, 2008

British Columbia, Victoria, Canada

Acceptance Rates

STOC '08 Paper Acceptance Rate 80 of 325 submissions, 25%;

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

12
Total Citations
View Citations
324
Total Downloads

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

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Kaufman TWigderson A(2016)Symmetric LDPC codes and local testingCombinatorica10.1007/s00493-014-2715-136:1(91-120)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1007/s00493-014-2715-1
Kaufman TWigderson A(2010)Symmetric LDPC codes and local testingProperty testing10.5555/1986603.1986631(312-319)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1986603.1986631
Kaufman TWigderson A(2010)Symmetric LDPC codes and local testingProperty testing10.5555/1980617.1980645(312-319)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1980617.1980645
Kaufman TViderman M(2010)Locally testable vs. locally decodable codesProceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniques10.5555/1886521.1886573(670-682)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.5555/1886521.1886573
Ben-Sasson EViderman M(2010)Low rate is insufficient for local testabilityProceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniques10.5555/1886521.1886555(420-433)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.5555/1886521.1886555
Kaufman TWigderson A(2010)Symmetric LDPC Codes and Local TestingProperty Testing10.1007/978-3-642-16367-8_25(312-319)Online publication date: 2010
https://doi.org/10.1007/978-3-642-16367-8_25
Gopalan PGuruswami VRaghavendra PMitzenmacher M(2009)List decoding tensor products and interleaved codesProceedings of the forty-first annual ACM symposium on Theory of computing10.1145/1536414.1536419(13-22)Online publication date: 31-May-2009
https://dl.acm.org/doi/10.1145/1536414.1536419
Ben-Sasson EGuruswami VKaufman TSudan MViderman M(2009)Locally Testable Codes Require Redundant TestersProceedings of the 2009 24th Annual IEEE Conference on Computational Complexity10.1109/CCC.2009.6(52-61)Online publication date: 15-Jul-2009
https://dl.acm.org/doi/10.1109/CCC.2009.6
Kopparty SSaraf S(2009)Tolerant Linearity Testing and Locally Testable CodesProceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-642-03685-9_45(601-614)Online publication date: 21-Aug-2009
https://dl.acm.org/doi/10.1007/978-3-642-03685-9_45
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