Distribution-Free Testing Lower Bound for Basic Boolean Functions

by Dana Glasner and Rocco A. Servedio

Theory of Computing, Volume 5(10), pp. 191-216, 2009

Bibliography with links to cited articles

[1]   N. Ailon and B. Chazelle: Information theory in property testing and monotonicity testing in higher dimension. Inform. and Comput., 204(11):1704–1717, 2006. [doi:10.1016/j.ic.2006.06.001].

[2]   N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron: Testing Reed-Muller Codes. IEEE Trans. Inform. Theory, 51(11):4032–4039, 2005. [doi:10.1109/TIT.2005.856958].

[3]   N. Alon and A. Shapira: Homomorphisms in Graph Property Testing - A Survey. In Topics in Discrete Mathematics, volume 26 of Algorithms and Combinatorics, pp. 281–313. Springer, 2006.

[4]   L. Babai, L. Fortnow, and C. Lund: Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Comput. Complexity, 1(1):3–40, 1991. [doi:10.1007/BF01200056].

[5]   M. Blum, M. Luby, and R. 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].

[6]   I. Diakonikolas, H. Lee, K. Matulef, K. Onak, R. Rubinfeld, R. Servedio, and A. Wan: Testing for Concise Representations. In Proc. 48th FOCS, pp. 549–558. IEEE Comp. Soc. Press, 2007. [FOCS:10.1109/FOCS.2007.32].

[7]   Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron, and A. Samorodnitsky: Improved Testing Algorithms for Monotonocity. In Proc. 3rd Intern. Workshop on Randomization and Approximation Techniques in Comp. Sci. (RANDOM’99), volume 1671 of Lecture Notes in Computer Science, pp. 97–108. Springer, 1999. [doi:10.1007/b72324].

[8]   E. Fischer: The Art of Uninformed Decisions: A Primer to Property Testing. Bull. Eur. Assoc. Theor. Comput. Sci., 75:97–126, 2001.

[9]   E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky: Testing juntas. J. Comput. System Sci., 68(4):753–787, 2004. [doi:10.1016/j.jcss.2003.11.004].

[10]   E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld, and A. Samorodnitsky: Monotonicity Testing Over General Poset Domains. In Proc. 34th STOC, pp. 474–483, 2002. [STOC:10.1145/509907.509977].

[11]   O. Goldreich: Combinatorial Property Testing – a survey. In Randomization Methods in Algorithm Design, pp. 45–60. AMS-DIMACS, 1998.

[12]   O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samordinsky: Testing Monotonicity. Combinatorica, 20(3):301–337, 2000. [doi:10.1007/s004930070011].

[13]   O. Goldreich, S. Goldwasser, and D. Ron: Property testing and its connection to learning and approximation. J. ACM, 45:653–750, 1998. [JACM:285055.285060].

[14]   S. Halevy and E. Kushilevitz: Distribution-Free Connectivity Testing for Sparse Graphs. Algorithmica, 51(1):24–48, 2004. [doi:10.1007/s00453-007-9054-1].

[15]   S. Halevy and E. Kushilevitz: A Lower Bound for Distribution-Free Monotonicity Testing. In Proc. 9th Intern. Workshop on Randomization and Approximation Techniques in Comp. Sci. (RANDOM’05), volume 3624 of Lecture Notes in Computer Science, pp. 330–341. Springer, 2005. [doi:10.1007/11538462_28].

[16]   S. Halevy and E. Kushilevitz: Distribution-Free Property Testing. SIAM J. Comput., 37(4):1107–1138, 2007. [SICOMP:10.1137/050645804].

[17]   M. Kearns and U. Vazirani: An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA, 1994.

[18]   K. Matulef, R. O’Donnell, R. Rubinfeld, and R. Servedio: Testing Halfspaces. In Proc. 19th Annual ACM-SIAM Symp. Dicrete Algorithms (SODA), pp. 256–264. ACM Press, 2009. [ACM:1496770.1496799].

[19]   M. Parnas, D. Ron, and A. Samorodnitsky: Testing Basic Boolean Formulae. SIAM J. Discrete Math., 16(1):20–46, 2002. [doi:10.1137/S0895480101407444].

[20]   D. Ron: Property Testing (A Tutorial). In Handbook of Randomized Computing, volume 2, pp. 597–649. Kluwer, 2000.

[21]   R. Rubinfeld: Sublinear time algorithms. In Proc. Intern. Congress of Mathematicians, volume 3, pp. 1095–1110. European Math. Soc., 2006.

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

[23]   G. Turán: Lower bounds for PAC learning with queries. In Proc. 6th Ann. Conf. Comput. Learning Theory, pp. 384–391. ACM Press, 1993. [ACM:10.1145/168304.168382].