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
This content will become publicly available on January 1, 2025
Testing Intersecting and UnionClosed Families
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
 Award ID(s):
 2107187
 NSFPAR ID:
 10521443
 Editor(s):
 Guruswami, Venkatesan
 Publisher / Repository:
 Schloss Dagstuhl – LeibnizZentrum für Informatik
 Date Published:
 Volume:
 287
 ISSN:
 18688969
 ISBN:
 9783959773096
 Page Range / eLocation ID:
 287287
 Subject(s) / Keyword(s):
 Sublinear algorithms property testing computational complexity monotonicity intersecting families unionclosed families Theory of computation → Streaming, sublinear and near linear time algorithms Mathematics of computing → Combinatorics
 Format(s):
 Medium: X Size: 23 pages; 1437198 bytes Other: application/pdf
 Size(s):
 23 pages 1437198 bytes
 Right(s):
 Creative Commons Attribution 4.0 International license; info:eurepo/semantics/openAccess
 Sponsoring Org:
 National Science Foundation
More Like this


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

Tauman_Kalai, Yael (Ed.)We show improved monotonicity testers for the Boolean hypercube under the pbiased measure, as well as over the hypergrid [m]ⁿ. Our results are: 1) For any p ∈ (0,1), for the pbiased hypercube we show a nonadaptive tester that makes Õ(√n/ε²) queries, accepts monotone functions with probability 1 and rejects functions that are εfar from monotone with probability at least 2/3. 2) For all m ∈ ℕ, we show an Õ(√nm³/ε²) query monotonicity tester over [m]ⁿ. We also establish corresponding directed isoperimetric inequalities in these domains, analogous to the isoperimetric inequality in [Subhash Khot et al., 2018]. Previously, the best known tester due to Black, Chakrabarty and Seshadhri [Hadley Black et al., 2018] had Ω(n^{5/6}) query complexity. Our results are optimal up to polylogarithmic factors and the dependency on m. Our proof uses a notion of monotone embeddings of measures into the Boolean hypercube that can be used to reduce the problem of monotonicity testing over an arbitrary product domains to the Boolean cube. The embedding maps a function over a product domain of dimension n into a function over a Boolean cube of a larger dimension n', while preserving its distance from being monotone; an embedding is considered efficient if n' is not much larger than n, and we show how to construct efficient embeddings in the above mentioned settings.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