Distribution-Free Testing for Monomials with a Sublinear Number of Queries

by Elya Dolev and Dana Ron

Theory of Computing, Volume 7(11), pp. 155-176, 2011

Bibliography with links to cited articles

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

[2]   H. Chernoff: A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist., 23(4):493–507, 1952. [doi:10.1214/aoms/1177729330]

[3]   Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, and Andrew Wan: Testing for concise representations. In Proc. 48th FOCS, pp. 549–557. IEEE Comp. Soc. Press, 2007. [doi:10.1109/FOCS.2007.32]

[4]   Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky: Improved testing algorithms for monotonocity. In Proc. 3rd Intern. Workshop Random. and Approx. Tech. Comput. Sci. (RANDOM), number 1671 in Lecture Notes in Comput. Sci., pp. 97–108. Springer, 1999. [doi:10.1007/978-3-540-48413-4_10]

[5]   Funda Ergün, Sampath Kannan, S. Ravi Kumar, Ronitt Rubinfeld, and Mahesh Viswanathan: Spot-checkers. J. Comput. System Sci., 60(3):717–751, 2000. [doi:10.1006/jcss.1999.1692]

[6]   Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky: Testing juntas. J. Comput. System Sci., 68(4):753–787, 2004. [doi:10.1016/j.jcss.2003.11.004]

[7]   Dana Glasner and Rocco A. Servedio: Distribution-free testing lower bounds for basic Boolean functions. Theory of Computing, 5(10):191–216, 2009. [doi:10.4086/toc.2009.v005a010]

[8]   Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodinsky: Testing monotonicity. Combinatorica, 20(3):301–337, 2000. [doi:10.1007/s004930070011]

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

[10]   Shirley Halevy and Eyal Kushilevitz: Distribution-free property-testing. SIAM J. Comput., 37(4):1107–1138, 2007. [doi:10.1137/050645804]

[11]   Shirley Halevy and Eyal Kushilevitz: Distribution-free connectivity testing for sparse graphs. Algorithmica, 51(1):24–48, 2008. [doi:10.1007/s00453-007-9054-1]

[12]   Shirley Halevy and Eyal Kushilevitz: Testing monotonicity over graph products. Random Structures Algorithms, 33(1):44–67, 2008. [doi:10.1002/rsa.20211]

[13]   Swastik Kopparty and Shubhangi Saraf: Tolerant linearity testing and locally testable codes. In Proc. 13th Intern. Workshop Random. and Approx. Tech. Comput. Sci. (RANDOM), number 5687 in Lecture Notes in Comput. Sci., pp. 601–614. Springer, 2009. [doi:10.1007/978-3-642-03685-9_45]

[14]   Kevin Matulef, Ryan O’Donnell, Ronitt Rubinfeld, and Rocco A. Servedio: Testing halfspaces. SIAM J. Comput., 39(5):2004–2047, 2010. [doi:10.1137/070707890]

[15]   Michal Parnas, Dana Ron, and Ronitt Rubinfeld: Tolerant property testing and distance approximation. J. Comput. System Sci., 72(6):1012–1042, 2006. [doi:10.1016/j.jcss.2006.03.002]

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

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

[18]   György Turán: Lower bounds for PAC learning with queries. In Proc. 6th Ann. ACM Conf. Comput. Learn. Theory (COLT), pp. 384–391. ACM Press, 1993. [doi:10.1145/168304.168382]

[19]   Leslie G. Valiant: A theory of the learnable. CACM, 27(11):1134–1142, November 1984. [doi:10.1145/1968.1972]