Document Open Access Logo

On Axis-Parallel Tests for Tensor Product Codes

Authors Alessandro Chiesa, Peter Manohar, Igor Shinkar

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.39.pdf
  • Filesize: 0.53 MB
  • 22 pages

Document Identifiers

Author Details

Alessandro Chiesa
Peter Manohar
Igor Shinkar

Cite As Get BibTex

Alessandro Chiesa, Peter Manohar, and Igor Shinkar. On Axis-Parallel Tests for Tensor Product Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 39:1-39:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.39

Abstract

Many low-degree tests examine the input function via its restrictions to random hyperplanes of a certain dimension. Examples include the line-vs-line (Arora, Sudan 2003), plane-vs-plane (Raz, Safra 1997), and cube-vs-cube (Bhangale, Dinur, Livni 2017) tests.

In this paper we study tests that only consider restrictions along axis-parallel hyperplanes, which have been studied by Polishchuk and Spielman (1994) and Ben-Sasson and Sudan (2006). While such tests are necessarily "weaker", they work for a more general class of codes, namely tensor product codes. Moreover, axis-parallel tests play a key role in constructing LTCs with inverse polylogarithmic rate and short PCPs (Polishchuk, Spielman 1994; Ben-Sasson, Sudan 2008; Meir 2010). We present two results on axis-parallel tests.

(1) Bivariate low-degree testing with low-agreement. We prove an analogue of the Bivariate Low-Degree Testing Theorem of Polishchuk and Spielman in the low-agreement regime, albeit with much larger field size. Namely, for the 2-wise tensor product of the Reed-Solomon code, we prove that for sufficiently large fields, the 2-query variant of the axis-parallel line test (row-vs-column test) works for arbitrarily small agreement. Prior analyses of axis-parallel tests assumed high agreement, and no results for such tests in the low-agreement regime were known.

Our proof technique deviates significantly from that of Polishchuk and Spielman, which relies on algebraic methods such as Bezout's Theorem, and instead leverages a fundamental result in extremal graph theory by Kovari, Sos, and Turan. To our knowledge, this is the first time this result is used in the context of low-degree testing.


(2) Improved robustness for tensor product codes. Robustness is a strengthening of local testability that underlies many applications. We prove that the axis-parallel hyperplane test for the m-wise tensor product of a linear code with block length n and distance d is Omega(d^m/n^m)-robust. This improves on a theorem of Viderman (2012) by a factor of 1/poly(m). While the improvement is not large, we believe that our proof is a notable simplification compared to prior work.

Subject Classification

Keywords
  • tensor product codes
  • locally testable codes
  • low-degree testing
  • extremal graph theory

Metrics

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

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. Google Scholar
  2. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM, 45(1):70-122, 1998. Preliminary version in FOCS'92. Google Scholar
  3. Sanjeev Arora and Madhu Sudan. Improved low-degree testing and its applications. Combinatorica, 23(3):365-426, 2003. Preliminary version appeared in STOC'97. 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'91, pages 21-32, 1991. Google Scholar
  5. László Babai, Lance Fortnow, and Carsten Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1:3-40, 1991. Preliminary version appeared in FOCS'90. Google Scholar
  6. Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, and Madhu Sudan. Linearity testing in characteristic two. IEEE Transactions on Information Theory, 42(6):1781-1795, 1996. Google Scholar
  7. Michael Ben-Or, Don Coppersmith, Mike Luby, and Ronitt Rubinfeld. Non-abelian homomorphism testing, and distributions close to their self-convolutions. Random Structures and Algorithms, 32(1):49-70, 2008. Google Scholar
  8. Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer. On the concrete efficiency of probabilistically-checkable proofs. In Proceedings of the 45th ACM Symposium on the Theory of Computing, STOC'13, pages 585-594, 2013. Google Scholar
  9. 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
  10. Eli Ben-Sasson and Madhu Sudan. Robust locally testable codes and products of codes. Random Structures and Algorithms, 28(4):387-402, 2006. Google Scholar
  11. Eli Ben-Sasson and Madhu Sudan. Short PCPs with polylog query complexity. SIAM Journal on Computing, 38(2):551-607, 2008. Preliminary version appeared in STOC'05. Google Scholar
  12. Eli Ben-Sasson, Madhu Sudan, Salil Vadhan, and Avi Wigderson. Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC'03, pages 612-621, 2003. Google Scholar
  13. Eli Ben-Sasson and Michael Viderman. Tensor products of weakly smooth codes are robust. In Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, and of the 12th International Workshop on Randomization and Computation, APPROX-RANDOM'08, pages 290-302, 2008. Google Scholar
  14. Eli Ben-Sasson and Michael Viderman. Composition of semi-LTCs by two-wise tensor products. Computational Complexity, 24(3):601-643, 2015. Google Scholar
  15. Amey Bhangale, Irit Dinur, and Inbal Livni Navon. Cube vs. cube low degree test. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference, ITCS'17, 2017. Google Scholar
  16. Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. Optimal testing of Reed-Muller codes. In Property Testing - Current Research, pages 269-275, 2010. Google Scholar
  17. 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
  18. Don Coppersmith and Atri Rudra. On the robust testability of product of codes, 2005. ECCC TR05-104. Google Scholar
  19. Irit Dinur and Omer Reingold. Assignment testers: Towards a combinatorial proof of the PCP theorem. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS'04, pages 155-164, 2004. Google Scholar
  20. Irit Dinur, Madhu Sudan, and Avi Wigderson. Robust local testability of tensor products of LDPC codes. In Proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, and of the 10th International Workshop on Randomization and Computation, APPROX-RANDOM'06, pages 304-315, 2006. Google Scholar
  21. Oded Goldreich and Or Meir. The tensor product of two good codes is not necessarily robustly testable. Information Processing Letters, 112(8-9):351-355, 2012. Google Scholar
  22. Oded Goldreich and Madhu Sudan. Locally testable codes and PCPs of almost-linear length. Journal of the ACM, 53:558-655, July 2006. Preliminary version in STOC'02. Google Scholar
  23. Johan Håstad. Some optimal inapproximability results. Journal of the ACM, 48(4):798-859, 2001. Google Scholar
  24. Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf. High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity. In Proceedings of the 48th ACM Symposium on the Theory of Computing, STOC'16, pages 202-215, 2016. Google Scholar
  25. T. Kövári, V. T. Sós, and P. Turán. On a problem of Zarankiewicz. Colloquium Mathematicae, 3:50-57, 1954. Google Scholar
  26. Or Meir. Combinatorial construction of locally testable codes. SIAM Journal on Computing, 39(2):491-544, 2009. Preliminary version appeared in STOC'08. Google Scholar
  27. Dana Moshkovitz and Ran Raz. Sub-constant error low degree test of almost-linear size. SIAM Journal on Computing, 38(1):140-180, 2008. Preliminary version in STOC'06. Google Scholar
  28. Alexander Polishchuk and Daniel A. Spielman. Nearly-linear size holographic proofs. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC'94, pages 194-203, 1994. Google Scholar
  29. Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, STOC'97, pages 475-484, 1997. Google Scholar
  30. Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252-271, 1996. Google Scholar
  31. Paul Valiant. The tensor product of two codes is not necessarily robustly testable. In Proceedings of the 8th International Workshop on Approximation, Randomization, and Combinatorial Optimization, APPROX-RANDOM'05, pages 472-481, 2005. Google Scholar
  32. Michael Viderman. A combination of testability and decodability by tensor products. In Proceedings of the 15th International Workshop on Approximation, Randomization, and Combinatorial Optimization, APPROX-RANDOM'12, pages 651-662, 2012. Google Scholar
  33. Michael Viderman. Strong ltcs with inverse poly-log rate and constant soundness. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS'13, pages 330-339, 2013. Google Scholar
  34. Jack Keil Wolf. On codes derivable from the tensor product of check matrices. IEEE Transactions on Information Theory, 11(2):281-284, 1965. Google Scholar
  35. Jack Keil Wolf and Bernard Elspas. Error-locating codes - a new concept in error control. IEEE Transactions on Information Theory, 9(2):113-117, 1963. Google Scholar
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 About DROPS Imprint Privacy Contact