An Optimal Lower Bound for Monotonicity Testing over Hypergrids

by Deeparnab Chakrabarty and C. Seshadhri

Theory of Computing, Volume 10(17), pp. 453-464, 2014

Bibliography with links to cited articles

[1]   Nir Ailon and Bernard Chazelle: Information theory in property testing and monotonicity testing in higher dimension. Inform. and Comput., 204(11):1704–1717, 2006. Preliminary version in STACS’05 and ECCC. [doi:10.1016/j.ic.2006.06.001]

[2]   Nir Ailon, Bernard Chazelle, S. Comandur, and Ding Liu: Estimating the distance to a monotone function. Random Structures Algorithms, 31(3):1704–1711, 2007. Preliminary version in RANDOM’04. [doi:10.1002/rsa.20167]

[3]   Tuğkan Batu, Ronitt Rubinfeld, and Patrick White: Fast approximate PCPs for multidimensional bin-packing problems. Inform. and Comput., 196(1):42–56, 2005. Preliminary version in APPROX’99. [doi:10.1016/j.ic.2004.10.001]

[4]   Eric Blais, Joshua Brody, and Kevin Matulef: Property testing lower bounds via communication complexity. Comput. Complexity, 21(2):311–358, 2012. Preliminary version in CCC’11 and ECCC. [doi:10.1007/s00037-012-0040-x]

[5]   Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev: Lower bounds for testing properties of functions on hypergrid domains. In Proc. 29th IEEE Conf. on Computational Complexity (CCC’14), pp. 309–320, 2014. Preliminary version in ECCC. [doi:10.1109/CCC.2014.38]

[6]   Béla Bollobás: Modern Graph Theory. Springer, 2000.

[7]   Dany Breslauer, Artur Czumaj, Devdatt P. Dubhashi, and Friedhelm Meyer auf der Heide: Transforming comparison model lower bounds to the parallel-random-access-machine. Inform. Process. Lett., 62(2):103–110, 1997. [doi:10.1016/S0020-0190(97)00032-X]

[8]   Jop Briët, Sourav Chakraborty, David García-Soriano, and Arjeh Matsliah: Monotonicity testing and shortest-path routing on the cube. Combinatorica, 32(1):35–53, 2012. Preliminary version in RANDOM’99 and ECCC. [doi:10.1007/s00493-012-2765-1]

[9]   Joshua Brody: Personal communication, 2013.

[10]   Deeparnab Chakrabarty and C. Seshadhri: Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids. In Proc. 45th STOC, pp. 419–428. ACM Press, 2013. Preliminary version in ECCC. [doi:10.1145/2488608.2488661]

[11]   Deeparnab Chakrabarty and C. Seshadhri: An optimal lower bound for monotonicity testing over hypergrids. In Proc. 16th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’13), pp. 425–435, 2013. Preliminary version in ECCC. [doi:10.1007/978-3-642-40328-6_30]

[12]   Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky: Improved testing algorithms for monotonicity. In Proc. 2nd Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’99), pp. 97–108, 1999. Available at ACM-DL. Preliminary version in ECCC.

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

[14]   Eldar Fischer: On the strength of comparisons in property testing. Inform. and Comput., 189(1):107–116, 2004. Preliminary version in ECCC. [doi:10.1016/j.ic.2003.09.003]

[15]   Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and Alex Samorodnitsky: Monotonicity testing over general poset domains. In Proceedings of the 34th Annual ACM Symposium on the Theory of Computing (STOC), pp. 474–483. ACM Press, 2002. [doi:10.1145/509907.509977]

[16]   Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky: Testing monotonicity. Combinatorica, 20:301–337, 2000. Preliminary version in FOCS’98. [doi:10.1007/s004930070011]

[17]   Oded Goldreich, Shafi Goldwasser, and Dana Ron: Property testing and its connection to learning and approximation. J. ACM, 45(4):653–750, 1998. Preliminary version in FOCS’96 and ECCC. [doi:10.1145/285055.285060]

[18]   Shirley Halevy and Eyal Kushilevitz: Testing monotonicity over graph products. Random Structures Algorithms, 33(1):44–67, 2008. Preliminary version in ICALP’04. [doi:10.1002/rsa.20211]

[19]   Eric Lehman and Dana Ron: On disjoint chains of subsets. J. Combin. Theory Ser. A, 94(2):399–404, 2001. [doi:10.1006/jcta.2000.3148]

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

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