Testing Monotonicity of Real-Valued Functions on DAGs

Abstract

We study monotonicity testing of real-valued functions on directed acyclic graphs (DAGs) with $n$ vertices. Let $m$ and $\ell$ be the numbers of edges in the transitive reduction and the transitive closure, respectively. For $1\le c\le d\le 2$, define $u(c,d):=\min \left\{\frac{1}{2},\frac{c}{3},\frac{c+d}{2}-1\right\}$. We show that every family of DAGs with $m=n^{c+o(1)}$ and $\ell =n^{d+o(1)}$ admits, for every fixed $\epsilon \in (0,1)$, a non-adaptive tester with one-sided error that uses $O_{\epsilon }(n^{u(c,d)+o(1)})$ queries. Conversely, we show that for every sufficiently small fixed $\epsilon >0$ and every fixed $(c,d)$, there are families of DAGs satisfying $m=n^{c+o(1)}$ and $\ell =n^{d+o(1)}$ on which every randomized non-adaptive tester, even with two-sided error, requires $n^{u(c,d)-o(1)}$ queries, making the upper bound tight up to a factor $n^{o(1)}$. Our main technical contribution is a lower-bound technique based on Ruzsa--Szemerédi families of positive matchings.

arXiv commentSubstantially revised. The adaptive lower bound claimed in the previous version could not be established and has been removed. The present version gives tight bounds for non-adaptive testers parameterized by the transitive reduction and closure