Monotonicity testing and shortest-path routing on the cube (Q452855)

This paper studies the complexity issue related to the problem of testing function monotonicity. In particular, the authors obtain tighter bounds for the associated complexities. Call a function \(f: {\{0, 1\}}^n \rightarrow {\mathcal R}\) disk-\(k\) monotone if \(f(y)>f(x)\) for every \(y>x,\) where \(| y| >| x| +k\). (Thus, ``disk-\(0\) monotone'' means ``monotone''.) The authors show in the Theorem\,4 that a disk-3 monotone function \(f\) can be tested for monotonicity with \(O(n^{3/2}/\epsilon)\) queries, where \(\epsilon>0.\) It is claimed that this bound is tighter than the best bound known prior to the publication of this paper, which depends on \({\mathcal R}\). The authors also further strengthen the lower bound of this problem from \(\Omega(\sqrt{n}/\epsilon)\) to \(\Omega(n/\epsilon)\) when \(| {\mathcal R}| >2\sqrt{n}.\) It is worth pointing out that the above upper bound was obtained by constructing a collection of source/target pairs in the \(n\)-dimension hypercube, commonly denoted as \(Q_n,\) such that no more than a \(1/\sqrt{n}\) fraction of these pairs can be simultaneously connected with edge-disjoint paths. Indeed, most of the results found in this paper are derived based on a known connection between this monotonicity testing problem and some routing problems associated with \(Q_n:\) if at least a \(\mu(n)\) fraction of any set of distinct source/target pairs on the directed version of \(Q_n\) can be connected with edge-disjoint paths, then the monotonicity of functions \(f: {\{0,1\}}^n \rightarrow \mathcal{R}\) can be tested with \(O(n/(\epsilon \mu(n)))\) queries for any totally ordered range \(\mathcal{R}.\)