Document Open Access Logo

Explicit Strong LTCs with Inverse Poly-Log Rate and Constant Soundness

Author Michael Viderman

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.58.pdf
  • Filesize: 468 kB
  • 14 pages

Document Identifiers

Author Details

Michael Viderman
  • Yahoo Research, Haifa, Israel

Cite AsGet BibTex

Michael Viderman. Explicit Strong LTCs with Inverse Poly-Log Rate and Constant Soundness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.58

Abstract

An error-correcting code C subseteq F^n is called (q,epsilon)-strong locally testable code (LTC) if there exists a tester that makes at most q queries to the input word. This tester accepts all codewords with probability 1 and rejects all non-codewords x not in C with probability at least epsilon * delta(x,C), where delta(x,C) denotes the relative Hamming distance between the word x and the code C. The parameter q is called the query complexity and the parameter epsilon is called soundness. Goldreich and Sudan (J.ACM 2006) asked about the existence of strong LTCs with constant query complexity, constant relative distance, constant soundness and inverse polylogarithmic rate. They also asked about the explicit constructions of these codes. Strong LTCs with the required range of parameters were obtained recently in the works of Viderman (CCC 2013, FOCS 2013) based on the papers of Meir (SICOMP 2009) and Dinur (J.ACM 2007). However, the construction of these codes was probabilistic. In this work we show that codes presented in the works of Dinur (J.ACM 2007) and Ben-Sasson and Sudan (SICOMP 2005) provide the explicit construction of strong LTCs with the above range of parameters. Previously, such codes were proven to be weak LTCs. Using the results of Viderman (CCC 2013, FOCS 2013) we prove that such codes are, in fact, strong LTCs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Interactive proof systems
Keywords
  • Error-Correcting Codes
  • Tensor Products
  • Locally Testable Codes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

  • The full version of this paper appeared as [Michael Viderman, 2015].

References

  1. Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing Reed-Muller codes. IEEE Transactions on Information Theory, 51(11):4032-4039, 2005. URL: http://dx.doi.org/10.1109/TIT.2005.856958.
  2. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof Verification and the Hardness of Approximation Problems. Journal of the ACM, 45(3):501-555, 1998. Google Scholar
  3. Sanjeev Arora and Shmuel Safra. Probabilistic Checking of Proofs: A New Characterization of NP. Journal of the ACM, 45(1):70-122, 1998. Google Scholar
  4. László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking Computations in Polylogarithmic Time. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC), May 5-8, 1991, New Orleans, Louisiana, USA, pages 21-31. ACM, 1991. URL: http://dx.doi.org/10.1145/103418.103428.
  5. M. Bellare, S. Goldwasser, C. Lund, and A. Russell. Efficient probabilistically checkable proofs and applications to approximation. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pages 294-304, New York, 1993. ACM SIGACT, ACM Press. Google Scholar
  6. Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free Bits, PCPs, and Nonapproximability - Towards Tight Results. SIAM Journal on Computing, 27(3):804-915, 1998. Google Scholar
  7. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM Journal on Computing, 36(4):889-974, 2006. Google Scholar
  8. Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, and Madhu Sudan. On sums of locally testable affine invariant properties. In Proceedings of Approximation, Randomization, and Combinatorial Optimization (APPROX-RANDOM), volume 6845 of Lecture Notes in Computer Science, pages 400-411. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22935-0.
  9. Eli Ben-Sasson, Noga Ron-Zewi, and Madhu Sudan. Sparse affine-invariant linear codes are locally testable. In FOCS, pages 561-570. IEEE Computer Society, 2012. URL: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6374356.
  10. Eli Ben-Sasson and Madhu Sudan. Robust locally testable codes and products of codes. Random Struct. Algorithms, 28(4):387-402, 2006. URL: http://dx.doi.org/10.1002/rsa.20120.
  11. Eli Ben-Sasson and Madhu Sudan. Short PCPs with polylog query complexity. SIAM J. Comput, 38(2):551-607, 2008. URL: http://dx.doi.org/10.1137/050646445.
  12. Eli Ben-Sasson and Michael Viderman. Composition of Semi-LTCs by Two-Wise Tensor Products. In Proceedings of Approximation, Randomization, and Combinatorial Optimization (APPROX-RANDOM), volume 5687 of Lecture Notes in Computer Science, pages 378-391. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-03685-9.
  13. Eli Ben-Sasson and Michael Viderman. Tensor Products of Weakly Smooth Codes are Robust. Theory of Computing, 5(1):239-255, 2009. URL: http://dx.doi.org/10.4086/toc.2009.v005a012.
  14. Eli Ben-Sasson and Michael Viderman. Low rate is insufficient for local testability. In Proceedings of Approximation, Randomization, and Combinatorial Optimization (APPROX-RANDOM), volume 6302 of Lecture Notes in Computer Science, pages 420-433. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15369-3.
  15. Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. Optimal testing of reed-muller codes. In FOCS, pages 488-497. IEEE Computer Society, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.54.
  16. Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences, 47(3):549-595, 1993. Google Scholar
  17. Don Coppersmith and Atri Rudra. On the Robust Testability of Product of Codes. Electronic Colloquium on Computational Complexity (ECCC), TR05-104, 2005. URL: http://eccc.hpi-web.de/eccc-reports/2005/TR05-104/index.html.
  18. Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM, 54(3):12:1-12:44, jun 2007. Google Scholar
  19. Irit Dinur and Omer Reingold. Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem. SIAM Journal on Computing, 36(4):975-1024, 2006. URL: http://dx.doi.org/10.1137/S0097539705446962.
  20. Irit Dinur, Madhu Sudan, and Avi Wigderson. Robust Local Testability of Tensor Products of LDPC Codes. In Proceedings of Approximation, Randomization, and Combinatorial Optimization (APPROX-RANDOM), volume 4110 of Lecture Notes in Computer Science, pages 304-315. Springer, 2006. URL: http://dx.doi.org/10.1007/11830924_29.
  21. Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43(2):268-292, 1996. URL: http://dx.doi.org/10.1145/226643.226652.
  22. Katalin Friedl and Madhu Sudan. Some improvements to total degree tests. In Third Israel Symposium on Theory of Computing and Systems, ISTCS 1995, Tel Aviv, Israel, January 4-6, 1995, Proceedings, pages 190-198, 1995. URL: http://dx.doi.org/10.1109/ISTCS.1995.377032.
  23. Oded Goldreich. Home page. http://www.wisdom.weizmann.ac.il/~oded/. URL: http://dl.acm.org/author_page.cfm?id=81336489395.
  24. Oded Goldreich. Short Locally Testable Codes and Proofs (Survey). Electronic Colloquium on Computational Complexity (ECCC), 2005. URL: http://eccc.hpi-web.de/eccc-reports/2005/TR05-014/index.html.
  25. Oded Goldreich and Or Meir. The tensor product of two good codes is not necessarily robustly testable. Inf. Process. Lett, 112(8-9):351-355, 2012. URL: http://dx.doi.org/10.1016/j.ipl.2012.01.007.
  26. Oded Goldreich and Dana Ron. On proximity-oblivious testing. SIAM J. Comput, 40(2):534-566, 2011. URL: http://dx.doi.org/10.1137/100789646.
  27. Oded Goldreich and Madhu Sudan. Locally testable codes and PCPs of almost-linear length. Journal of the ACM, 53(4):558-655, 2006. URL: http://dx.doi.org/10.1145/1162349.1162351.
  28. Elena Grigorescu, Tali Kaufman, and Madhu Sudan. Succinct representation of codes with applications to testing. SIAM J. Discrete Math, 26(4):1618-1634, 2012. URL: http://dx.doi.org/10.1137/100818364.
  29. Johan Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798-859, 2001. URL: http://dx.doi.org/10.1145/502090.502098.
  30. Tali Kaufman and Shachar Lovett. New Extension of the Weil Bound for Character Sums with Applications to Coding. In IEEE 52nd Annual Symposium on Foundations of Computer Science, (FOCS), pages 788-796. IEEE, 2011. URL: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120.
  31. Tali Kaufman and Dana Ron. Testing polynomials over general fields. SIAM J. Comput, 36(3):779-802, 2006. URL: http://dx.doi.org/10.1137/S0097539704445615.
  32. Tali Kaufman and Madhu Sudan. Sparse Random Linear Codes are Locally Decodable and Testable. In FOCS, pages 590-600. IEEE Computer Society, 2007. URL: http://dx.doi.org/10.1109/FOCS.2007.65.
  33. Tali Kaufman and Madhu Sudan. Algebraic property testing: the role of invariance. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), Victoria, British Columbia, Canada, May 17-20, 2008, pages 403-412. ACM, 2008. URL: http://dx.doi.org/10.1145/1374376.1374434.
  34. Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. High-rate locally correctable and locally testable codes with sub-polynomial query complexity. J. ACM, 64(2):11:1-11:42, 2017. URL: http://dx.doi.org/10.1145/3051093.
  35. Swastik Kopparty and Shubhangi Saraf. Local list-decoding and testing of random linear codes from high error. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pages 417-426. ACM, 2010. URL: http://dx.doi.org/10.1145/1806689.1806748.
  36. Or Meir. Combinatorial Construction of Locally Testable Codes. SIAM J. Comput, 39(2):491-544, 2009. URL: http://dx.doi.org/10.1137/080729967.
  37. Noga Ron-Zewi and Madhu Sudan. A new upper bound on the query complexity for testing generalized reed-muller codes. In Proceedings of Approximation, Randomization, and Combinatorial Optimization (APPROX-RANDOM), volume 7408 of Lecture Notes in Computer Science, pages 639-650. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-32512-0.
  38. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252-271, 1996. URL: http://dx.doi.org/10.1137/S0097539793255151.
  39. Luca Trevisan. Some Applications of Coding Theory in Computational Complexity, 2004. URL: http://arxiv.org/abs/cs/0409044.
  40. Paul Valiant. The Tensor Product of Two Codes Is Not Necessarily Robustly Testable. In Proceedings of Approximation, Randomization, and Combinatorial Optimization (APPROX-RANDOM), volume 3624 of Lecture Notes in Computer Science, pages 472-481. Springer, 2005. URL: http://dx.doi.org/10.1007/11538462_40.
  41. Michael Viderman. A combination of testability and decodability by tensor products. In Proceedings of Approximation, Randomization, and Combinatorial Optimization (APPROX-RANDOM), volume 7408 of Lecture Notes in Computer Science, pages 651-662. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-32512-0.
  42. Michael Viderman. Strong LTCs with inverse poly-log rate and constant soundness. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, Berkeley, CA, USA, 26-29 October, 2013, pages 330-339, 2013. Google Scholar
  43. Michael Viderman. Strong LTCs with inverse polylogarithmic rate and soundness. In Proceedings of the 28th Conference on Computational Complexity, CCC, Palo Alto, California, USA, 5-7 June, 2013, pages 255-265, 2013. Google Scholar
  44. Michael Viderman. Explicit strong ltcs with inverse poly-log rate and constant soundness. Electronic Colloquium on Computational Complexity (ECCC), 22:20, 2015. URL: http://eccc.hpi-web.de/report/2015/020.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact