@inbook {IOPORT.05783917,
    author       = {Bri\"et, Jop and Chakraborty, Sourav and Garc{\'\i}a-Soriano, David and Matsliah, Arie},
    title        = {Monotonicity testing and shortest-path routing on the cube.},
    year         = {2010},
    booktitle    = {Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 13th international workshop, APPROX 2010, and 14th international workshop, RANDOM 2010, Barcelona, Spain, September 1--3, 2010. Proceedings},
    isbn         = {978-3-642-15368-6},
    pages        = {462-475},
    publisher    = {Berlin: Springer},
    doi          = {10.1007/978-3-642-15369-3_35},
    abstract     = {Summary: 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/\epsilon )$ queries, for any totally ordered range ${\mathcal R}$. More generally, if at least a $\mu (n)$ fraction of the pairs can always be connected with edge-disjoint paths then the query complexity is $O(n/(\epsilon \mu (n)) )$. We construct a family of instances of $\Omega (2^{n })$ 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 $\approx 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 $\delta > 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 $\Omega (n/\epsilon )$ 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.},
    identifier   = {05783917},
}