Testing Monotonicity of Real-Valued Functions on DAGs

We study monotonicity testing of real-valued functions on directed acyclic graphs (DAGs) with $n$ vertices. For every constant $\delta >0$, we prove a $\mathrm{\Omega }(n^{1\mathrm{/}2-\delta }\mathrm{/}\sqrt{\epsilon })$ lower bound against non-adaptive two-sided testers on DAGs, nearly matching the classical $O(\sqrt{n\mathrm{/}\epsilon })$-query upper bound. For constant $\epsilon$, we also prove an $\mathrm{\Omega }(\sqrt{n})$ lower bound for randomized adaptive one-sided testers on explicit bipartite DAGs, whereas previously only an $\mathrm{\Omega }(\log n)$ lower bound was known. A key technical ingredient in both lower bounds is positive-matching Ruzsa–Szemerédi families. On the algorithmic side, we give simple non-adaptive one-sided testers with query complexity $O(\sqrt{m\mathrm{\ell }}\mathrm{/}(\epsilon n))$ and $O(m^{1\mathrm{/}3}\mathrm{/}{\epsilon }^{2\mathrm{/}3})$, where $m$ is the number of edges in the transitive reduction and $\mathrm{\ell }$ is the number of edges in the transitive closure. For constant $\epsilon >0$, these improve over the previous $O(\sqrt{n\mathrm{/}\epsilon })$ bound when $m\mathrm{\ell }=o(n^3)$ and $m=o(n^{3\mathrm{/}2})$, respectively.