Abstract
We study the problem of monotonicity testing over the hypercube. As previously observed in several works, a positive answer to a natural question about routing properties of the hypercube network would imply the existence of efficient monotonicity testers. In particular, if any set of source-sink pairs on the directed hypercube (with all sources and all sinks distinct) can be connected with edge-disjoint paths, then monotonicity of functions \(f:{\{0,1\}}^n \rightarrow {\mathcal R}\) can be tested with O(n/ε) queries, for any totally ordered range \({\mathcal R}\). More generally, if at least a μ(n) fraction of the pairs can always be connected with edge-disjoint paths then the query complexity is O(n/(εμ(n)) ).
We construct a family of instances of Ω(2n) pairs in n-dimensional hypercubes such that no more than roughly a \(\frac{1}{\sqrt{n}}\) fraction of the pairs can be simultaneously connected with edge-disjoint paths. This answers an open question of Lehman and Ron [LR01], and suggests that the aforementioned appealing combinatorial approach for deriving query-complexity upper bounds from routing properties cannot yield, by itself, query-complexity bounds better than ≈ n 3/2. Additionally, our construction can also be used to obtain a strong counterexample to Szymanski’s conjecture about routing on the hypercube. In particular, we show that for any δ> 0, the n-dimensional hypercube is not \(n^{\frac 12 -\delta}\)-realizable with shortest paths, while previously it was only known that hypercubes are not 1-realizable with shortest paths.
We also prove a lower bound of Ω(n/ε) queries for one-sided non-adaptive testing of monotonicity over the n-dimensional hypercube, as well as additional bounds for specific classes of functions and testers.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Al-Bashabsheh, A., Yongaçoglu, A.: On the k-pairs problem. CoRR, abs/0805.0050 (2008)
Ailon, N., Chazelle, B.: Information theory in property testing and monotonicity testing in higher dimension. Inf. Comput. 204(11), 1704–1717 (2006)
Adler, M., Harvey, N.J.A., Jain, K., Kleinberg, R.D., Lehman, A.R.: On the capacity of information networks. In: SODA, pp. 241–250 (2006)
Benes, V.E.: Mathematical theory of connecting networks and telephone traffic. Academic Press, New York (1965)
Bhattacharyya, A., Grigorescu, E., Jung, K., Raskhodnikova, S., Woodruff, D.: Transitive-closure spanners. In: SODA 2009: Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, pp. 932–941. Society for Industrial and Applied Mathematics, Philadelphia (2009)
Bhattacharyya, A., Grigorescu, E., Jung, K., Raskhodnikova, S., Woodruff, D.: Transitive-closure spanners of the hypercube and the hypergrid. Electronic Colloquium on Computational Complexity (ECCC) 09(046) (2009)
Bhattacharyya, A.: A note on the distance to monotonicity of boolean functions. Electronic Colloquium on Computational Complexity (ECCC) 15(012) (2008)
Dodis, Y., Goldreich, O., Lehman, E., Raskhodnikova, S., Ron, D., Samorodnitsky, A.: Improved testing algorithms for monotonicity. In: Hochbaum, D.S., Jansen, K., Rolim, J.D.P., Sinclair, A. (eds.) RANDOM 1999 and APPROX 1999. LNCS, vol. 1671, pp. 97–108. Springer, Heidelberg (1999)
Ergün, F., Kannan, S., Kumar, R., Rubinfeld, R., Viswanathan, M.: Spot-checkers. J. Comput. Syst. Sci. 60(3), 717–751 (2000)
Fischer, E.: On the strength of comparisons in property testing. Inf. Comput. 189(1), 107–116 (2004)
Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R., Samorodnitsky, A.: Monotonicity testing over general poset domains. In: STOC, pp. 474–483 (2002)
Goldreich, O., Goldwasser, S., Lehman, E., Ron, D., Samorodnitsky, A.: Testing monotonicity. Combinatorica 20(3), 301–337 (2000)
Goldreich, O., Goldwasser, S., Lehman, E., Ron, D.: Testing monotonicity. In: FOCS, pp. 426–435 (1998)
Halevy, S., Kushilevitz, E.: Testing monotonicity over graph products. Random Struct. Algorithms 33(1), 44–67 (2008)
Lehman, E., Ron, D.: On disjoint chains of subsets. J. Comb. Theory, Ser. A 94(2), 399–404 (2001)
Lubiw, A.: Counterexample to a conjecture of szymanski on hypercube routing. Inf. Process. Lett. 35(2), 57–61 (1990)
Raskhodnikova, S.: Monotonicity testing. Master’s thesis, Department of Electrical Engineering and Computer Science. MIT, Cambridge, MA (1999)
Rasala-Lehman, A.: Network coding. PhD thesis, Department of Electrical Engineering and Computer Science. MIT, Cambridge, MA (2005)
Szymanski, T.H.: On the permutation capability of a circuit-switched hypercube. In: ICPP (1), pp. 103–110 (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Briët, J., Chakraborty, S., García-Soriano, D., Matsliah, A. (2010). Monotonicity Testing and Shortest-Path Routing on the Cube. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. RANDOM APPROX 2010 2010. Lecture Notes in Computer Science, vol 6302. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15369-3_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-15369-3_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15368-6
Online ISBN: 978-3-642-15369-3
eBook Packages: Computer ScienceComputer Science (R0)