ECCC-Report TR10-048https://eccc.weizmann.ac.il/report/2010/048Comments and Revisions published for TR10-048en-usWed, 24 Mar 2010 16:52:49 +0200
Paper TR10-048
| Monotonicity Testing and Shortest-Path Routing on the Cube |
David GarcĂa Soriano,
Arie Matsliah,
Sourav Chakraborty,
Jop Briet
https://eccc.weizmann.ac.il/report/2010/048We 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.
Wed, 24 Mar 2010 16:52:49 +0200https://eccc.weizmann.ac.il/report/2010/048