TR10-048 Authors: David GarcĂa Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

Publication: 24th March 2010 16:52

Downloads: 2516

Keywords:

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 $\ell$ disjoint source-sink pairs

on the directed hypercube can be connected with edge-disjoint

paths, then monotonicity of functions $f:\zo^n \to \RR$ can be tested

with $O(n)$ queries, for {\em any} totally ordered range $\RR$. More

generally, if at least an $\alpha(n)$ fraction of the pairs can

always be connected with edge-disjoint paths then the query-complexity

is $O(n/\alpha(n))$.

We construct a family of instances of $\ell=\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

\cite{le_ro}, 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 on routing in 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.