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 November 6, 2024
A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$Dimensional Hypergrids
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
 Award ID(s):
 1908384
 NSFPAR ID:
 10488871
 Publisher / Repository:
 IEEE
 Date Published:
 Journal Name:
 Annual Symposium on Foundations of Computer Science
 ISSN:
 02725428
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


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

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

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