article

A combination of testability and decodability by tensor products

Author:

Michael VidermanAuthors Info & Claims

Random Structures & Algorithms, Volume 46, Issue 3

Pages 572 - 598

https://doi.org/10.1002/rsa.20498

Published: 01 May 2015 Publication History

Abstract

No abstract available.

References

[1]

N.Alon, J.Bruck, J.Naor, M.Naor, and R. M.Roth, Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs IEEE Trans Inform Theory Volume 38 1992, pp.509-516.

Digital Library

Google Scholar

[2]

N.Alon, T.Kaufman, T. M.Krivelevich, S.Litsyn, and D.Ron, Testing reed-muller codes, IEEE Trans Inform Theory Volume 51 2005, pp.4032-4039.

Digital Library

Google Scholar

[3]

S.Arora, C.Lund, R.Motwani, M.Sudan, and M.Szegedy, Proof verification and the hardness of approximation problems, J ACM Volume 45 1998, pp.501-555.

Digital Library

Google Scholar

[4]

S.Arora and S.Safra, Probabilistic checking of proofs: A, new characterization of NP, J ACM Volume 45 1998, pp.70-122.

Digital Library

Google Scholar

[5]

S.Arora and M.Sudan, Improved low-degree testing and its applications, Combinatorica Volume 23 2003, pp.365-426.

Crossref

Google Scholar

[6]

L.Babai, L.Fortnow, L. A.Levin, and M.Szegedy, Checking computations in polylogarithmic time, In Proc. 23rd STOC, ACM, New Orleans, Louisiana, USA, 1991. pp. pp.21-31.

Digital Library

Google Scholar

[7]

L.Babai, L.Fortnow, and C.Lund, Non-deterministic exponential time has two-prover interactive protocols, Comput Complex Volume 1 1991, pp.3-40.

Crossref

Google Scholar

[8]

L.Babai, L.Fortnow, N.Nisan, and A.Wigderson, BPP has subexponential time simulations unless EXPTIME has publishable proofs, Comput Complex Volume 3 1993, pp.307-318.

Digital Library

Google Scholar

[9]

E.Ben-Sasson, O.Goldreich, P.Harsha, M.Sudan, and S. P.Vadhan, Robust PCPs of proximity, shorter PCPs, and applications to coding, SIAM J Comput Volume 36 2006, pp.889-974.

Digital Library

Google Scholar

[10]

E.Ben-Sasson, P.Harsha, and S.Raskhodnikova, Some 3CNF properties are hard to test, SIAM J Comput Volume 35 2005, pp.1-21.

Digital Library

Google Scholar

[11]

E.Ben-Sasson and M.Sudan, Simple PCPs with poly-log rate and query complexity, In STOC, ACM, Baltimore, MD, USA, 2005, pp. pp.266-275.

Digital Library

Google Scholar

[12]

E.Ben-Sasson and M.Sudan, Robust locally testable codes and products of codes, Random Struct Algorithms Volume 28 2006, pp.387-402.

Digital Library

Google Scholar

[13]

E.Ben-Sasson and M.Viderman, Composition of semi-LTCs by two-wise tensor products, In I.Dinur, K.Jansen, J.Naor, and J. D. P.Rolim Editors, Springer, Berkeley, CA, USA, 2009, pp. pp.378-391.

Digital Library

Google Scholar

[14]

E.Ben-Sasson and M.Viderman, Tensor products of weakly smooth codes are robust, Theory Comput Volume 5 2009, pp.239-255.

Crossref

Google Scholar

[15]

E.Ben-Sasson and M.Viderman, Low rate is insufficient for local testability, In M. J.Serna, R.Shaltiel, K.Jansen, and J. D. P.Rolim Editors, Springer, Barcelona, Spain, 2010, pp. pp.420-433.

Digital Library

Google Scholar

[16]

M.Blum, M.Luby, and R.Rubinfeld, Self-testing/correcting with applications to numerical problems, J Comput Syst Sci Volume 47 1993, pp.549-595.

Digital Library

Google Scholar

[17]

B.Chor, O.Goldreich, E.Kushilevitz, and M.Sudan, Private information retrieval, J ACM Volume 45 1998, pp.965-981.

Digital Library

Google Scholar

[18]

D.Coppersmith and A.Rudra, On the robust testability of product of codes, In Electronic Colloquium on Computational Complexity Volume 104 2005.

Google Scholar

[19]

I.Dinur, The PCP, theorem by gap amplification, J ACM Volume 54 2007, pp.12:1-12:44.

Digital Library

Google Scholar

[20]

I.Dinur and O.Reingold, Assignment testers: towards a combinatorial proof of the PCP theorem, SIAM J Comput Volume 36 2006, pp.975-1024.

Digital Library

Google Scholar

[21]

I.Dinur, M.Sudan, and A.Wigderson, Robust local testability of tensor products of LDPC codes, In APPROX-RANDOM, Vol. 4110 of Lecture Notes in Computer Science, Springer, Barcelona, Spain, 2006, pp. pp.304-315.

Digital Library

Google Scholar

[22]

K.Efremenko, 3-query locally decodable codes of subexponential length, In M.Mitzenmacher Editor, ACM, Bethesda, MD, USA, 2009, pp. pp.39-44.

Digital Library

Google Scholar

[23]

O.Goldreich, Short locally testable codes and proofs survey, In Electronic Colloquium on Computational Complexity ECCC Volume 014 2005.

Google Scholar

[24]

O.Goldreich and O.Meir, The tensor product of two good codes is not necessarily robustly testable, Inform Process Lett Volume 112 2012, pp.351-355.

Digital Library

Google Scholar

[25]

O.Goldreich and M.Sudan, Locally testable codes and PCPs of almost-linear length, J ACM Volume 53 2006, pp.558-655.

Digital Library

Google Scholar

[26]

P.Gopalan, V.Guruswami, and P.Raghavendra, List decoding tensor products and interleaved codes, In M.Mitzenmacher Editor, ACM, Bethesda, MD, USA, 2009, pp. pp.13-22.

Digital Library

Google Scholar

[27]

V.Guruswami and P.Indyk, Linear time encodable and list decodable codes, In STOC, ACM, San Diego, CA, USA, 2003, pp. pp.126-135.

Digital Library

Google Scholar

[28]

V.Guruswami and P.Indyk, Linear-time encodable/decodable codes with near-optimal rate, IEEE Trans Inform Theory Volume 51 2005, pp.3393-3400.

Digital Library

Google Scholar

[29]

R.Impagliazzo and A.Wigderson, P=BPP if E requires exponential circuits: Derandomizing the XOR lemma, In STOC, ACM Press, New York, USA, 1997, pp. pp.220-229.

Digital Library

Google Scholar

[30]

T.Kaufman and M.Sudan, Sparse random linear codes are locally decodable and testable, In FOCS, IEEE Computer Society, Providence, Rhode Island, 2007, pp. pp.590-600.

Digital Library

Google Scholar

[31]

T.Kaufman and M.Sudan, Algebraic property testing: the role of invariance, In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, ACM, Victoria, British Columbia, Canada, 2008, pp. pp.403-412.

Digital Library

Google Scholar

[32]

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, Springer, Barcelona, Spain, 2010, pp. pp.670-682.

Digital Library

Google Scholar

[33]

S.Kopparty and S.Saraf, Local list-decoding and testing of random linear codes from high error, In Leonard J.Schulman Editor, ACM, Cambridge, MA, USA, 2010, pp. pp.17-426.

Digital Library

Google Scholar

[34]

S.Kopparty, S.Saraf, and S.Yekhanin, High-rate codes with sublinear-time decoding, In ECCC-TR10-148, 2010.

Google Scholar

[35]

R. J.Lipton, Efficient checking of computations, In 7th Annual Symposium on Theoretical Aspects of Computer Science STACS 90, Vol. 415 of Lecture Notes in Computer Science, Springer, Berlin-Heidelberg, New York, 1990, pp. pp.207-215.

Digital Library

Google Scholar

[36]

C.Lund, L.Fortnow, H. J.Karloff, and N.Nisan, Algebraic methods for interactive proof systems, J ACM Volume 39 1992, pp.859-868.

Digital Library

Google Scholar

[37]

O.Meir, Combinatorial Construction of Locally Testable Codes, SIAM J Comput Volume 39 2009, pp.491-544.

Digital Library

Google Scholar

[38]

O.Meir, IP=PSPACE using error correcting codes, In Electronic Colloquium on Computational Complexity ECCC, Vol. Volume 17, 2010, pp. pp.137

Google Scholar

[39]

O.Meir, On the rectangle method in proofs of robustness of tensor products, Inform Process Lett Volume 112 2012, pp.257-260.

Digital Library

Google Scholar

[40]

D.Moshkovitz and R.Raz, Two-query PCP, with subconstant error, J ACM Volume 57 2010.

Digital Library

Google Scholar

[41]

R.Raz and S.Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, In STOC, ACM Press, New York, USA, 1997, pp. pp.475-484.

Digital Library

Google Scholar

[42]

I. S.Reed, A class of multiple-error-correcting codes and the decoding scheme, IEEE Trans Inform Theory Volume 4 1954, pp.38-49.

Crossref

Google Scholar

[43]

R. M.Roth, Introduction to coding theory, Cambridge University Press, Cambridge, MA, USA, 2006.

Digital Library

Google Scholar

[44]

R. M.Roth and V.Skachek, Improved nearly-MDS expander codes, IEEE Trans Inform Theory Volume 52 pp.3650-3661.

Digital Library

Google Scholar

[45]

R.Shaltiel and C.Umans, Simple extractors for all min-entropies and a new pseudorandom generator, J ACM Volume 52 2005, pp.172-216.

Digital Library

Google Scholar

[46]

A.Shamir, IP=PSPACE, J ACM Volume 39 1992, pp.869-877.

Digital Library

Google Scholar

[47]

A.Shen, IP=PSPACE: Simplified proof, J ACM Volume 39 1992, pp.878-880.

Digital Library

Google Scholar

[48]

M.Sipser and D. A.Spielman, Expander codes, IEEE Trans Inform Theory Volume 42 1996, pp.1710-1722, Preliminary version appeared in FOCS 1994.

Crossref

Google Scholar

[49]

D. A.Spielman, Linear-time encodable and decodable error-correcting codes, IEEE Trans Inform Theory Volume 42 1996, pp.1723-1731, Preliminary version appeared in STOC 1995.

Crossref

Google Scholar

[50]

M.Sudan, L.Trevisan, and S. P.Vadhan, Pseudorandom generators without the XOR lemma, J Comput Syst Sci Volume 62 2001, pp.236-266.

Digital Library

Google Scholar

[51]

L.Trevisan, Some applications of coding theory in computational complexity, In Electronic Colloquium on Computational Complexity ECCC Volume 043 2004.

Google Scholar

[52]

P.Valiant, The tensor product of two codes is not necessarily robustly testable, In APPROX-RANDOM, Vol. 3624 of Lecture Notes in Computer Science, Springer, 2005, pp. pp.472-481.

Digital Library

Google Scholar

[53]

S.Yekhanin, Towards 3-query locally decodable codes of subexponential length, J ACM Volume 55 2008, pp.1-16.

Digital Library

Google Scholar

Cited By

View all

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
Ron-Zewi NWeiss M(2024)Zero-Knowledge IOPs Approaching Witness LengthAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68403-6_4(105-137)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68403-6_4
Augot DBordage SNardi J(2022)Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codesDesigns, Codes and Cryptography10.1007/s10623-022-01134-z91:3(1111-1151)Online publication date: 13-Nov-2022
https://dl.acm.org/doi/10.1007/s10623-022-01134-z
Show More Cited By

Recommendations

Decoding interleaved Reed-Solomon codes over noisy channels

We consider error correction over the Non-Binary Symmetric Channel (NBSC) which is a natural probabilistic extension of the Binary Symmetric Channel (BSC). We propose a new decoding algorithm for interleaved Reed-Solomon codes that attempts to correct ...
List decoding tensor products and interleaved codes
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes. (1) We show that for every code, the ratio of its list decoding radius to its minimum distance stays unchanged ...
Composition of semi-LTCs by two-wise tensor products

In this paper, we obtain a composition theorem that allows us to construct locally testable codes (LTCs) by repeated two-wise tensor products. This is the first composition theorem showing that repeating the two-wise tensor operation any constant number ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Random Structures & Algorithms

Random Structures & Algorithms Volume 46, Issue 3

May 2015

202 pages

ISSN:1042-9832

EISSN:1098-2418

Issue’s Table of Contents

Publisher

John Wiley & Sons, Inc.

United States

Publication History

Published: 01 May 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
Ron-Zewi NWeiss M(2024)Zero-Knowledge IOPs Approaching Witness LengthAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68403-6_4(105-137)Online publication date: 18-Aug-2024
Augot DBordage SNardi J(2022)Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codesDesigns, Codes and Cryptography10.1007/s10623-022-01134-z91:3(1111-1151)Online publication date: 13-Nov-2022
Holmgren JRothblum R(2022)Faster Sounder Succinct Arguments and sAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15802-5_17(474-503)Online publication date: 15-Aug-2022
Kopparty SResch NRon-Zewi NSaraf SSilas S(2020)On List Recovery of High-Rate Tensor CodesIEEE Transactions on Information Theory10.1109/TIT.2020.302396267:1(296-316)Online publication date: 18-Dec-2020
Bootle JChiesa AGroth J(2020)Linear-Time Arguments with Sublinear Verification from Tensor CodesTheory of Cryptography10.1007/978-3-030-64378-2_2(19-46)Online publication date: 16-Nov-2020
Rubinstein A(2019)Hardness of Approximation Between P and NPundefinedOnline publication date: 30-May-2019
Kopparty SMeir ORon-Zewi NSaraf S(2017)High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query ComplexityJournal of the ACM10.1145/305109364:2(1-42)Online publication date: 25-May-2017
Kopparty SSaraf S(2016)Guest ColumnACM SIGACT News10.1145/2993749.299376147:3(46-66)Online publication date: 31-Aug-2016
Kopparty SMeir ORon-Zewi NSaraf SWichs DMansour Y(2016)High-rate locally-correctable and locally-testable codes with sub-polynomial query complexityProceedings of the forty-eighth annual ACM symposium on Theory of Computing10.1145/2897518.2897523(202-215)Online publication date: 19-Jun-2016

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

Decoding interleaved Reed-Solomon codes over noisy channels

List decoding tensor products and interleaved codes

Composition of semi-LTCs by two-wise tensor products

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations