Monotonicity testing and shortest-path routing on the cube (Q452855): Difference between revisions

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}.\)