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
Nonadaptive vs Adaptive Queries in the Dense Graph Testing Model
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
 Award ID(s):
 1900460
 NSFPAR ID:
 10339955
 Date Published:
 Journal Name:
 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
 Page Range / eLocation ID:
 269 to 275
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


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

Uniformity testing is one of the most wellstudied problems in property testing, with many known test statistics, including ones based on counting collisions, singletons, and the empirical TV distance. It is known that the optimal sample complexity to distinguish the uniform distribution on m elements from any ϵfar distribution with 1−δ probability is n=Θ(mlog(1/δ)√ϵ2+log(1/δ)ϵ2), which is achieved by the empirical TV tester. Yet in simulation, these theoretical analyses are misleading: in many cases, they do not correctly rank order the performance of existing testers, even in an asymptotic regime of all parameters tending to 0 or ∞. We explain this discrepancy by studying the \emph{constant factors} required by the algorithms. We show that the collisions tester achieves a sharp maximal constant in the number of standard deviations of separation between uniform and nonuniform inputs. We then introduce a new tester based on the Huber loss, and show that it not only matches this separation, but also has tails corresponding to a Gaussian with this separation. This leads to a sample complexity of (1+o(1))mlog(1/δ)√ϵ2 in the regime where this term is dominant, unlike all other existing testers.more » « less

We present a sublinear time algorithm that allows one to sample multiple edges from a distribution that is pointwise ϵclose to the uniform distribution, in an amortizedefficient fashion. We consider the adjacency list query model, where access to a graph G is given via degree and neighbor queries. The problem of sampling a single edge in this model has been raised by Eden and Rosenbaum (SOSA 18). Let n and m denote the number of vertices and edges of G, respectively. Eden and Rosenbaum provided upper and lower bounds of Θ∗(n/ √ m) for sampling a single edge in general graphs (where O ∗(·) suppresses poly(1/ϵ) and poly(log n) dependencies). We ask whether the query complexity lower bound for sampling a single edge can be circumvented when multiple samples are required. That is, can we get an improved amortized persample cost if we allow a preprocessing phase? We answer in the affirmative. We present an algorithm that, if one knows the number of required samples q in advance, has an overall cost that is sublinear in q, namely, O∗(√ q · (n/ √ m)), which is strictly preferable to O∗(q · (n/ √ m)) cost resulting from q invocations of the algorithm by Eden and Rosenbaum. Subsequent to a preliminary version of this work, Tětek and Thorup (arXiv, preprint) proved that this bound is essentially optimal.more » « less

There has been significant study on the sample complexity of testing properties of distributions over large domains. For many properties, it is known that the sample complexity can be substantially smaller than the domain size. For example, over a domain of size n, distinguishing the uniform distribution from distributions that are far from uniform in ℓ1distance uses only O(n−−√) samples. However, the picture is very different in the presence of arbitrary noise, even when the amount of noise is quite small. In this case, one must distinguish if samples are coming from a distribution that is ϵclose to uniform from the case where the distribution is (1−ϵ)far from uniform. The latter task requires nearly linear in n samples (Valiant, 2008; Valiant and Valiant, 2017a). In this work, we present a noise model that on one hand is more tractable for the testing problem, and on the other hand represents a rich class of noise families. In our model, the noisy distribution is a mixture of the original distribution and noise, where the latter is known to the tester either explicitly or via sample access; the form of the noise is also known \emph{a priori}. Focusing on the identity and closeness testing problems leads to the following mixture testing question: Given samples of distributions p,q1,q2, can we test if p is a mixture of q1 and q2? We consider this general question in various scenarios that differ in terms of how the tester can access the distributions, and show that indeed this problem is more tractable. Our results show that the sample complexity of our testers are exactly the same as for the classical nonmixture case.more » « less