Monotonicity testing of Boolean functions on the hypergrid, $f:[n]^d \to \{0,1\}$, is a classic topic in property testing. Determining the nonadaptive complexity of this problem is an important open question. For arbitrary $n$, [BlackChakrabartySeshadhri, SODA 2020] describe a tester with query complexity $\widetilde{O}(\varepsilon^{4/3}d^{5/6})$. This complexity is independent of $n$, but has a suboptimal dependence on $d$. Recently, [BravermanKhotKindlerMinzer, ITCS 2023] and [BlackChakrabartySeshadhri, STOC 2023] describe $\widetilde{O}(\varepsilon^{2} n^3\sqrt{d})$ and $\widetilde{O}(\varepsilon^{2} n\sqrt{d})$query testers, respectively. These testers have an almost optimal dependence on $d$, but a suboptimal polynomial dependence on $n$. \smallskip In this paper, we describe a nonadaptive, onesided monotonicity tester with query complexity $O(\varepsilon^{2} d^{1/2 + o(1)})$, \emph{independent} of $n$. Up to the $d^{o(1)}$factors, our result resolves the nonadaptive complexity of monotonicity testing for Boolean functions on hypergrids. The independence of $n$ yields a nonadaptive, onesided $O(\varepsilon^{2} d^{1/2 + o(1)})$query monotonicity tester for Boolean functions $f:\mathbb{R}^d \to \{0,1\}$ associated with an arbitrary product measure.
more »
« less
Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $~O(n\sqrt{d})$ Monotonicity Tester
The problem of testing monotonicity for Boolean functions on the hypergrid, $f:[n]^d \to \{0,1\}$ is a classic topic in property testing. When $n=2$, the domain is the hypercube. For the hypercube case, a breakthrough result of KhotMinzerSafra (FOCS 2015) gave a nonadaptive, onesided tester making $\otilde(\eps^{2}\sqrt{d})$ queries. Up to polylog $d$ and $\eps$ factors, this bound matches the $\widetilde{\Omega}(\sqrt{d})$query nonadaptive lower bound (ChenDeServedioTan (STOC 2015), ChenWaingartenXie (STOC 2017)). For any $n > 2$, the optimal nonadaptive complexity was unknown. A previous result of the authors achieves a $\otilde(d^{5/6})$query upper bound (SODA 2020), quite far from the $\sqrt{d}$ bound for the hypercube. In this paper, we resolve the nonadaptive complexity of monotonicity testing for all constant $n$, up to $\poly(\eps^{1}\log d)$ factors. Specifically, we give a nonadaptive, onesided monotonicity tester making $\otilde(\eps^{2}n\sqrt{d})$ queries. From a technical standpoint, we prove new directed isoperimetric theorems over the hypergrid $[n]^d$. These results generalize the celebrated directed Talagrand inequalities that were only known for the hypercube.
more »
« less
 Award ID(s):
 1908384
 NSFPAR ID:
 10488868
 Publisher / Repository:
 ACM
 Date Published:
 Journal Name:
 Proceedings of the annual ACM Symposium on Theory of Computing
 ISSN:
 07378017
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


A Boolean {\em $k$monotone} function defined over a finite poset domain ${\cal D}$ alternates between the values $0$ and $1$ at most $k$ times on any ascending chain in ${\cal D}$. Therefore, $k$monotone functions are natural generalizations of the classical {\em monotone} functions, which are the {\em $1$monotone} functions. Motivated by the recent interest in $k$monotone functions in the context of circuit complexity and learning theory, and by the central role that monotonicity testing plays in the context of property testing, we initiate a systematic study of $k$monotone functions, in the property testing model. In this model, the goal is to distinguish functions that are $k$monotone (or are close to being $k$monotone) from functions that are far from being $k$monotone. Our results include the following: \begin{enumerate} \item We demonstrate a separation between testing $k$monotonicity and testing monotonicity, on the hypercube domain $\{0,1\}^d$, for $k\geq 3$; \item We demonstrate a separation between testing and learning on $\{0,1\}^d$, for $k=\omega(\log d)$: testing $k$monotonicity can be performed with $2^{O(\sqrt d \cdot \log d\cdot \log{1/\eps})}$ queries, while learning $k$monotone functions requires $2^{\Omega(k\cdot \sqrt d\cdot{1/\eps})}$ queries (Blais et al. (RANDOM 2015)). \item We present a tolerant test for functions $f\colon[n]^d\to \{0,1\}$ with complexity independent of $n$, which makes progress on a problem left open by Berman et al. (STOC 2014). \end{enumerate} Our techniques exploit the testingbylearning paradigm, use novel applications of Fourier analysis on the grid $[n]^d$, and draw connections to distribution testing techniques.more » « less

Guruswami, Venkatesan (Ed.)Inspired by the classic problem of Boolean function monotonicity testing, we investigate the testability of other wellstudied properties of combinatorial finite set systems, specifically intersecting families and unionclosed families. A function f: {0,1}ⁿ → {0,1} is intersecting (respectively, unionclosed) if its set of satisfying assignments corresponds to an intersecting family (respectively, a unionclosed family) of subsets of [n]. Our main results are that  in sharp contrast with the property of being a monotone set system  the property of being an intersecting set system, and the property of being a unionclosed set system, both turn out to be informationtheoretically difficult to test. We show that:  For ε ≥ Ω(1/√n), any nonadaptive twosided εtester for intersectingness must make 2^{Ω(n^{1/4}/√{ε})} queries. We also give a 2^{Ω(√{n log(1/ε)})}query lower bound for nonadaptive onesided εtesters for intersectingness.  For ε ≥ 1/2^{Ω(n^{0.49})}, any nonadaptive twosided εtester for unionclosedness must make n^{Ω(log(1/ε))} queries. Thus, neither intersectingness nor unionclosedness shares the poly(n,1/ε)query nonadaptive testability that is enjoyed by monotonicity. To complement our lower bounds, we also give a simple poly(n^{√{nlog(1/ε)}},1/ε)query, onesided, nonadaptive algorithm for εtesting each of these properties (intersectingness and unionclosedness). We thus achieve nearly tight upper and lower bounds for twosided testing of intersectingness when ε = Θ(1/√n), and for onesided testing of intersectingness when ε = Θ(1).more » « less

We design a nonadaptive algorithm that, given a Boolean function f: {0, 1}^n → {0, 1} which is αfar from monotone, makes poly(n, 1/α) queries and returns an estimate that, with high probability, is an Otilde(\sqrt{n})approximation to the distance of f to monotonicity. Furthermore, we show that for any constant k > 0, approximating the distance to monotonicity up to n^(1/2−k)factor requires 2^{n^k} nonadaptive queries, thereby ruling out a poly(n, 1/α)query nonadaptive algorithm for such approximations. This answers a question of Seshadhri (Property Testing Review, 2014) for the case of nonadaptive algorithms. Approximating the distance to a property is closely related to tolerantly testing that property. Our lower bound stands in contrast to standard (nontolerant) testing of monotonicity that can be done nonadaptively with Otilde(n/ε^2) queries. We obtain our lower bound by proving an analogous bound for erasureresilient testers. An αerasureresilient tester for a desired property gets oracle access to a function that has at most an α fraction of values erased. The tester has to accept (with probability at least 2/3) if the erasures can be filled in to ensure that the resulting function has the property and to reject (with probability at least 2/3) if every completion of erasures results in a function that is εfar from having the property. Our method yields the same lower bounds for unateness and being a kjunta. These lower bounds improve exponentially on the existing lower bounds for these properties.more » « less

We study the relation between the query complexity of adaptive and nonadaptive testers in the dense graph model. It has been known for a couple of decades that the query complexity of nonadaptive testers is at most quadratic in the query complexity of adaptive testers. We show that this general result is essentially tight; that is, there exist graph properties for which any nonadaptive tester must have query complexity that is almost quadratic in the query complexity of the best general (i.e., adaptive) tester. More generally, for every q: N→N such that q(n)≤n−−√ and constant c∈[1,2], we show a graph property that is testable in Θ(q(n)) queries, but its nonadaptive query complexity is Θ(q(n)c), omitting poly(log n) factors and ignoring the effect of the proximity parameter ϵ. Furthermore, the upper bounds hold for onesided error testers, and are at most quadratic in 1/ϵ. These results are obtained through the use of general reductions that transport properties of ordered structured (like bit strings) to those of unordered structures (like unlabeled graphs). The main features of these reductions are queryefficiency and preservation of distance to the properties. This method was initiated in our prior work (ECCC, TR20149), and we significantly extend it here.more » « less