Testing Linear-Invariant Non-Linear Properties

by Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie

Theory of Computing, Volume 7(6), pp. 75-99, 2011

Bibliography with links to cited articles

[1]   Noga Alon, Eldar Fischer, Ilan Newman, and Asaf Shapira: A combinatorial characterization of the testable graph properties: It’s all about regularity. SIAM J. Comput., 39:143–167, 2009. [doi:10.1137/060667177]

[2]   Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron: Testing low-degree polynomials over GF(2). In Proc. Approx. Random. Comb. Opt. (RANDOM ’03), volume 2764 of Lecture Notes in Computer Science, pp. 188–199. Springer, 2003. [doi:10.1007/978-3-540-45198-3_17]

[3]   Noga Alon, Michael Krivelevich, Ilan Newman, and Mario Szegedy: Regular languages are testable with a constant number of queries. SIAM J. Comput., 30(6):1842–1862, 2000. [doi:10.1137/S0097539700366528]

[4]   Noga Alon and Asaf Shapira: A characterization of the (natural) graph properties testable with one-sided error. In Proc. 46th FOCS, pp. 429–438. IEEE Comp. Soc. Press, 2005. [doi:10.1109/SFCS.2005.5]

[5]   Noga Alon and Asaf Shapira: Every monotone graph property is testable. In Proc. 37th STOC, pp. 128–137. ACM Press, 2005. [doi:10.1145/1060590.1060611]

[6]   Noga Alon and Asaf Shapira: Homomorphisms in graph property testing - a survey. Technical Report 085, Electron. Colloq. on Comput. Complexity (ECCC), 2005. [ECCC:TR05-085]

[7]   Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998. [doi:10.1145/278298.278306]

[8]   Sanjeev Arora and Shmuel Safra: Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70–122, 1998. [doi:10.1145/273865.273901]

[9]   László Babai, Lance Fortnow, and Carsten Lund: Non-deterministic exponential time has two-prover interactive protocols. Comput. Complexity, 1(1):3–40, 1991. [doi:10.1007/BF01200430]

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

[11]   Mihir Bellare, Oded Goldreich, and Madhu Sudan: Free bits, PCPs, and nonapproximability—towards tight results. SIAM J. Comput., 27(3):804–915, 1998. [doi:10.1137/S0097539796302531]

[12]   Vitaly Bergelson, Terence Tao, and Tamar Ziegler: An inverse theorem for the uniformity seminorms associated with the action of Fω. Geom. Funct. Anal., 19:1539–1596, 2010. [doi:10.1007/s00039-010-0051-1]

[13]   Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie: Testing linear-invariant non-linear properties: A short report. Technical Report 10-116, Electron. Colloq. on Comput. Complexity (ECCC), July 2010. [ECCC:TR10-116]

[14]   Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, and Ning Xie: Separations of matroid freeness properties. Technical Report 10-136, Electron. Colloq. on Comput. Complexity (ECCC), August 2010. [ECCC:TR10-136]

[15]   Arnab Bhattacharyya, Elena Grigorescu, and Asaf Shapira: A unified framework for testing linear-invariant properties. In Proc. 51st FOCS, pp. 478–487. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.53]

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

[17]   Christian Borgs, Jennifer T. Chayes, László Lovász, Vera T. Sós, Balázs Szegedy, and Katalin Vesztergombi: Graph limits and parameter testing. In Proc. 38th STOC, pp. 261–270. ACM Press, 2006. [doi:10.1145/1132516.1132556]

[18]   Victor Chen, Madhu Sudan, and Ning Xie: Property testing via set-theoretic operations. In Proc. 2nd Symp. Innov. Comput. Sci. (ICS ’11), pp. 211–222, 2011.

[19]   Oded Goldreich, Shafi Goldwasser, and Dana Ron: Property testing and its connection to learning and approximation. J. ACM, 45(4):653–750, 1998. [doi:10.1145/285055.285060]

[20]   Timothy Gowers and Julia Wolf: The true complexity of a system of linear equations. Technical Report 0711.0185, arXiv e-print archive, 2007. [arXiv:0711.0185]

[21]   Ben Green: A Szemerédi-type regularity lemma in abelian groups, with applications. Geom. Funct. Anal., 15(2):340–376, 2005. [doi:10.1007/s00039-005-0509-8]

[22]   Ben Green and Terence Tao: Linear equations in primes. Ann. of Math., 171(3):1753–1850, 2010. [doi:10.4007/annals.2010.171.1753]

[23]   Johan Håstad: Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. [doi:10.1145/502090.502098]

[24]   Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, and David Zuckerman: Testing low-degree polynomials over prime fields. In Proc. 45th FOCS, pp. 423–432. IEEE Comp. Soc. Press, 2004. [doi:10.1109/FOCS.2004.64]

[25]   Tali Kaufman and Dana Ron: Testing polynomials over general fields. In Proc. 45th FOCS, pp. 413–422. IEEE Comp. Soc. Press, 2004. [doi:10.1109/FOCS.2004.64]

[26]   Tali Kaufman and Madhu Sudan: Algebraic property testing: The role of invariance. In Proc. 40th STOC, pp. 403–412. ACM Press, 2008. [doi:10.1145/1374376.1374434]

[27]   Daniel Král’, Oriol Serra, and Lluís Vena: A removal lemma for systems of linear equations over finite fields. Technical Report 0809.1846, arxiv e-print archive, 2008. [arXiv:0809.1846]

[28]   Daniel Král’, Oriol Serra, and Lluís Vena: A combinatorial proof of the removal lemma for groups. J. Combin. Theory Ser. A, 116(4):971–978, 2009. [doi:10.1016/j.jcta.2008.12.003]

[29]   Michal Parnas, Dana Ron, and Alex Samorodnitsky: Testing basic Boolean formulae. SIAM J. Discrete Math., 16(1):20–46, 2003. [doi:10.1137/S0895480101407444]

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

[31]   Alex Samorodnitsky and Luca Trevisan: Gowers uniformity, influence of variables, and PCPs. In Proc. 38th STOC, pp. 11–20, New York, NY, USA, 2006. ACM Press. [doi:10.1145/1132516.1132519]

[32]   Asaf Shapira: Green’s conjecture and testing linear-invariant properties. In Proc. 41st STOC, pp. 159–166. ACM Press, 2009. [doi:10.1145/1536414.1536438]

[33]   Terence Tao and Tamar Ziegler: The inverse conjecture for the Gowers norm over finite fields via the correspondence principle. Analysis & PDE, 3(1):1–20, 2010. [doi:10.2140/apde.2010.3.1]

[34]   William T. Tutte: Matroids and graphs. Trans. Amer. Math. Soc., 90:527–552, 1959. [doi:10.2307/1993185]

[35]   Dominic J.A. Welsh: Matroid Theory. Academic Press Inc., London, 1976.