Exponentially Small Soundness for the Direct Product Z-test

by Irit Dinur and Inbal Livni Navon

Theory of Computing, Volume 19(3), pp. 1-56, 2023

Bibliography with links to cited articles

[1]   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, ECCC:TR97-003]

[2]   Vitaly Bergelson, Terence Tao, and Tamar Ziegler: An inverse theorem for the uniformity seminorms associated with the action of Fp. Geom. Funct. Anal. (GAFA), 19(6):1539–1596, 2010. [doi:10.1007/s00039-010-0051-1, arXiv:0901.2602]

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

[4]   Irit Dinur: The PCP theorem by gap amplification. J. ACM, 54(3):12, 2007. Preliminary version in STOC’06. [doi:10.1145/1236457.1236459, ECCC:TR05-046]

[5]   Irit Dinur and Elazar Goldenberg: Locally testing direct product in the low error range. In Proc. 49th FOCS, pp. 613–622. IEEE Comp. Soc., 2008. [doi:10.1109/FOCS.2008.26]

[6]   Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra: Towards a proof of the 2-to-1 games conjecture? In Proc. 50th STOC, pp. 376–389. ACM Press, 2018. [doi:10.1145/3188745.3188804, ECCC:TR16-198]

[7]   Irit Dinur and Inbal Livni Navon: Exponentially small soundness for the direct product Z-test. In Proc. 32nd Comput. Complexity Conf. (CCC’17), pp. 29:1–50. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.CCC.2017.29]

[8]   Irit Dinur and David Steurer: Direct product testing. In Proc. 29th IEEE Conf. on Comput. Complexity (CCC’14), pp. 188–196. IEEE Comp. Soc., 2014. [doi:10.1109/CCC.2014.27, ECCC:TR13-179]

[9]   Oded Goldreich and Shmuel Safra: A combinatorial consistency lemma with application to proving the PCP theorem. SIAM J. Comput., 29(4):1132–1154, 2000. Preliminary version in RANDOM’97. [doi:10.1137/S0097539797315744, ECCC:TR96-047]

[10]   Torben Hagerup and Christine Rüb: A guided tour of Chernoff bounds. Inform. Process. Lett., 33(6):305–308, 1990. [doi:10.1016/0020-0190(90)90214-I]

[11]   Wassily Hoeffding: Probability inequalities for sums of bounded random variables. J. Amer. Statistical Association, 58(301):13–30, 1963. Also available in The Collected Works of Wassily Hoeffding, 1994, pp. 409–426, Springer and at JSTOR. [doi:10.1080/01621459.1963.10500830]

[12]   Russell Impagliazzo and Valentine Kabanets: Constructive proofs of concentration bounds. In Proc. 14th Internat. Workshop on Randomization and Computation (RANDOM’10), pp. 617–631. Springer, 2010. [doi:10.1007/978-3-642-15369-3_46]

[13]   Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson: New direct-product testers and 2-query PCPs. SIAM J. Comput., 41(6):1722–1768, 2012. Preliminary version in STOC’09. [doi:10.1137/09077299X, ECCC:TR09-090]

[14]   Subhash Khot, Dor Minzer, and Muli Safra: On independent sets, 2-to-2 games, and Grassmann graphs. In Proc. 49th STOC, pp. 576–589. ACM Press, 2017. [doi:10.1145/3055399.3055432, ECCC:TR16-124]

[15]   Michael Mitzenmacher and Eli Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge Univ. Press, 2005. [doi:10.1017/CBO9780511813603]

[16]   Elchanan Mossel, Krzysztof Oleszkiewicz, and Arnab Sen: On reverse hypercontractivity. Geom. Funct. Anal. (GAFA), 23(3):1062–1097, 2013. [doi:10.1007/s00039-013-0229-4, arXiv:1108.1210]

[17]   Alessandro Panconesi and Aravind Srinivasan: Randomized distributed edge coloring via an extension of the chernoff-hoeffding bounds. SIAM J. Comput., 26(2):350–368, 1997. [doi:10.1137/S0097539793250767]

[18]   Ran Raz: A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998. Preliminary version in STOC’95. [doi:10.1137/S0097539795280895]

[19]   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]