On Axis-Parallel Tests for Tensor Product Codes

by Alessandro Chiesa, Peter Manohar, and Igor Shinkar

Theory of Computing, Volume 16(5), pp. 1-34, 2020

Bibliography with links to cited articles

[1]   Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron: Testing Reed-Muller codes. IEEE Trans. Inform. Theory, 51(11):4032–4039, 2005. Preliminary version in RANDOM’03. [doi:10.1109/TIT.2005.856958]

[2]   Sanjeev Arora and Shmuel Safra: Probabilistic checking of proofs: a new characterization of NP. J. ACM, 45(1):70–122, 1998. Preliminary version in FOCS’92. [doi:10.1145/273865.273901]

[3]   Sanjeev Arora and Madhu Sudan: Improved low-degree testing and its applications. Combinatorica, 23(3):365–426, 2003. Preliminary version in STOC’97. [doi:10.1007/s00493-003-0025-0]

[4]   Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, and S. Raja: Randomized polynomial-time identity testing for noncommutative circuits. Theory of Computing, 15(7):1–36, 2019. [doi:10.4086/toc.2019.v015a007]

[5]   László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy: Checking computations in polylogarithmic time. In Proc. 23rd STOC, pp. 21–32. ACM Press, 1991. [doi:10.1145/103418.103428]

[6]   László Babai, Lance Fortnow, and Carsten Lund: Non-deterministic exponential time has two-prover interactive protocols. Comput. Complexity, 1:3–40, 1991. Preliminary version in FOCS’90. [doi:10.1007/BF01200056]

[7]   Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, and Madhu Sudan: Linearity testing in characteristic two. IEEE Trans. Inform. Theory, 42(6):1781–1795, 1996. Preliminary version in FOCS’95. [doi:10.1109/18.556674]

[8]   Michael Ben-Or, Don Coppersmith, Mike Luby, and Ronitt Rubinfeld: Non-Abelian homomorphism testing, and distributions close to their self-convolutions. Random Structures Algorithms, 32(1):49–70, 2008. Preliminary version in RANDOM’04. [doi:10.1002/rsa.20182]

[9]   Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer: On the concrete efficiency of probabilistically-checkable proofs. In Proc. 45th STOC, pp. 585–594. ACM Press, 2013. [doi:10.1145/2488608.2488681]

[10]   Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan: Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput., 36(4):889–974, 2006. Preliminary version in STOC’04. [doi:10.1137/S0097539705446810]

[11]   Eli Ben-Sasson and Madhu Sudan: Robust locally testable codes and products of codes. Random Structures Algorithms, 28(4):387–402, 2006. Preliminary version in RANDOM’04. [doi:10.1002/rsa.20120, arXiv:cs/0408066]

[12]   Eli Ben-Sasson and Madhu Sudan: Short PCPs with polylog query complexity. SIAM J. Comput., 38(2):551–607, 2008. Preliminary version in STOC’05. [doi:10.1137/050646445]

[13]   Eli Ben-Sasson, Madhu Sudan, Salil Vadhan, and Avi Wigderson: Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. In Proc. 35th STOC, pp. 612–621. ACM Press, 2003. [doi:10.1145/780542.780631]

[14]   Eli Ben-Sasson and Michael Viderman: Tensor products of weakly smooth codes are robust. Theory of Computing, 5(12):239–255, 2009. Preliminary version in RANDOM’08. [doi:10.4086/toc.2009.v005a012]

[15]   Eli Ben-Sasson and Michael Viderman: Composition of semi-LTCs by two-wise tensor products. Comput. Complexity, 24(3):601–643, 2015. Preliminary version in RANDOM’09. [doi:10.1007/s00037-013-0074-8]

[16]   Amey Bhangale, Irit Dinur, and Inbal Livni Navon: Cube vs. cube low degree test. In Proc. 8th Innovations in Theoret. Comp. Sci. (ITCS’17), pp. 40:1–40:31. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.ITCS.2017.40, arXiv:1612.07491]

[17]   Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman: Optimal testing of Reed-Muller codes. In Property Testing, pp. 269–275, 2010. Preliminary version in FOCS’10. [doi:10.1007/978-3-642-16367-8_19, arXiv:0910.0641]

[18]   Manuel Blum, Michael Luby, and Ronitt Rubinfeld: Self-testing/correcting with applications to numerical problems. J. Comput. System Sci., 47(3):549–595, 1993. Preliminary version in STOC’90. [doi:10.1016/0022-0000(93)90044-W]

[19]   Alessandro Chiesa, Peter Manohar, and Igor Shinkar: On axis-parallel tests for tensor product codes. In Proc. 21st Internat. Workshop on Randomization and Computation (RANDOM’17), pp. 472–481. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.APPROX-RANDOM.2017.39]

[20]   Don Coppersmith and Atri Rudra: On the robust testability of product of codes. Electron. Colloq. on Comput. Complexity (ECCC), 2005. [ECCC:TR05-104]

[21]   Irit Dinur and Omer Reingold: Assignment testers: Towards a combinatorial proof of the PCP theorem. SIAM J. Comput., 36:975–1024, 2006. Preliminary version in FOCS’04. [doi:10.1137/S0097539705446962]

[22]   Irit Dinur, Madhu Sudan, and Avi Wigderson: Robust local testability of tensor products of LDPC codes. pp. 304–315. [doi:10.1007/11830924_29]

[23]   Oded Goldreich: Short locally testable codes and proofs: A survey in two parts. In Property Testing, pp. 65–104. Springer, 2010. [doi:10.1007/978-3-642-16367-8_6]

[24]   Oded Goldreich and Or Meir: The tensor product of two good codes is not necessarily robustly testable. Inform. Process. Lett., 112(8-9):351–355, 2012. [doi:10.1016/j.ipl.2012.01.007]

[25]   Oded Goldreich and Madhu Sudan: Locally testable codes and PCPs of almost-linear length. J. ACM, 53(4):558–655, 2006. Preliminary version in FOCS’02. [doi:10.1145/1162349.1162351]

[26]   Johan Håstad: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. Preliminary version in STOC’97. [doi:10.1145/502090.502098]

[27]   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. Preliminary version in STOC’16. [doi:10.1145/3051093, arXiv:1504.05653]

[28]   Tamás K˝o   vári, Vera T. Sós, and Pál Turán: On a problem of K. Zarankiewicz. Colloquium Mathematicae, 3:50–57, 1954. Accessible at the Hungarian Acad. Sci.

[29]   Or Meir: Combinatorial construction of locally testable codes. SIAM J. Comput., 39(2):491–544, 2009. Preliminary version in STOC’08. [doi:10.1137/080729967]

[30]   Dana Moshkovitz and Ran Raz: Sub-constant error low degree test of almost-linear size. SIAM J. Comput., 38(1):140–180, 2008. Preliminary version in STOC’06. [doi:10.1137/060656838]

[31]   Alexander Polishchuk and Daniel A. Spielman: Nearly-linear size holographic proofs. In Proc. 26th STOC, pp. 194–203. ACM Press, 1994. [doi:10.1145/195058.195132]

[32]   Ran Raz and Shmuel Safra: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proc. 29th STOC, pp. 475–484. ACM Press, 1997. [doi:10.1145/258533.258641]

[33]   Ronitt Rubinfeld and Madhu Sudan: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252–271, 1996. [doi:10.1137/S0097539793255151]

[34]   Paul Valiant: The tensor product of two codes is not necessarily robustly testable. In Proc. 9th Internat. Workshop on Randomization and Computation (RANDOM’05), pp. 472–481. Springer, 2005. [doi:10.1007/11538462_40]

[35]   Michael Viderman: A combination of testability and decodability by tensor products. Random Structures Algorithms, 46(3):572–598, 2013. Preliminary version in RANDOM’12. [doi:10.1002/rsa.20498, arXiv:1105.5806]

[36]   Michael Viderman: Strong LTCs with inverse poly-log rate and constant soundness. In Proc. 54th FOCS, pp. 330–339. IEEE Comp. Soc. Press, 2013. [doi:10.1109/FOCS.2013.43]

[37]   Jack Keil Wolf: On codes derivable from the tensor product of check matrices. IEEE Trans. Inform. Theory, 11(2):281–284, 1965. [doi:10.1109/TIT.1965.1053771]

[38]   Jack Keil Wolf and Bernard Elspas: Error-locating codes – a new concept in error control. IEEE Trans. Inform. Theory, 9(2):113–117, 1963. [doi:10.1109/TIT.1963.1057813]