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]