We initiate a systematic study of the computational complexity of property testing, focusing on the relationship between query and time complexity. While traditional work in property testing has emphasized query complexity—often via information-theoretic techniques—relatively little is known about the computational hardness of property testers. Our goal is to chart the landscape of time-query interplay and develop tools for proving time complexity lower bounds. Our first contribution is a pair of time-query hierarchy theorems for property testing. For all suitable nondecreasing functions \(q(n)\) and \(t(n)\) with \(t(n) \ge q(n)\), we construct properties with query complexity \(\tilde \Theta(q(n))\) and time complexity \(\tilde \Omega(t(n))\). Our weak hierarchy holds unconditionally, whereas the strong version—assuming the Strong Exponential Time Hypothesis— provides better control over the time complexity of the constructed properties.

Motivated by the challenge of testing distributions over continuous or high-dimensional domains, we study distribution testing with respect to bounded classes of distinguishers. A representative task is to use samples from an unknown distribution P over a very large domain to decide between two cases: P = Pref for a fixed reference distribution Pref, or there exists a distinguisher f in a bounded class F which witnesses the separation |EP[f] − EPref[f]| > є. This is the task of identity testing with respect to fooling distance, a name inspired by the conceptual connection with pseudorandomness. (Formally, our model instantiates integral probability metrics from Boolean classes of bounded expressivity.)

We study the spectral gap of subgraphs of the hypercube induced by monotone subsets of vertices. For a monotone subset $A\subseteq\{0,1\}^{n}$ of density $μ(A)$, the previous best lower bound on the spectral gap, due to Cohen, was $γ\gtrsim μ(A)/n^{2}$, improving upon the earlier bound $γ\gtrsim μ(A)^{2}/n^{2}$ established by Ding and Mossel. In this paper, we prove the optimal lower bound $γ\gtrsim μ(A)/n$. As a corollary, we improve the mixing time upper bound of the random walk on constant-density monotone sets from $O(n^{3})$, as shown by Ding and Mossel, to $O(n^{2})$. Along the way, we develop two new inequalities that may be of independent interest: (1)~a directed $L^{2}$-Poincaré inequality on the hypercube, and (2)~an ``approximate'' FKG inequality for monotone sets.

Consider two problems about an unknown probability distribution 𝑝: (1) How many samples from 𝑝 are required to test if 𝑝 is supported on 𝑛 elements or not? Specifically, given samples from 𝑝, determine whether it is supported on at most 𝑛 elements, or it is “𝜀-far” (in total variation distance) from being supported on 𝑛 elements. (2) Given𝑚 samples from 𝑝, what is the largest lower bound on its support size that we can produce? The best known upper bound for problem (1) uses a general algorithm for learning the histogram of the distribution 𝑝, which requires Θ( 𝑛 𝜀2 log𝑛) samples .We showthat testing can be done more efficiently than learning the histogram, using only𝑂( 𝑛 𝜀 log𝑛 log(1/𝜀)) samples, nearly matching the best known lower bound of Ω( 𝑛 𝜀 log𝑛). This algorithm also provides a better solution to problem (2), producing larger lower bounds on support size than what follows from previous work. The proof relies on an analysis of Chebyshev polynomial approximations outside the range where they are designed to be good approximations.

This paper explores the connection between classical isoperimetric inequalities, their directed analogues, and mono-tonicity testing. We study the setting of real-valued functions$f:[0, 1]^{d}\rightarrow\mathbb{R}$on the solid unit cube, where the goal is to test with respect to the$L^{p}$distance. Ourgoals are twofold: to further understand the relationship between classical and directed isoperimetry, and to give a monotonicity tester with sublinear query complexity in this setting, Our main results are 1) an$L^{2}$monotonicity tester for$M$-Lipschitz functions with query complexity$O(\sqrt{d}M^{2}/\varepsilon^{2})$and, behind this result, 2) the directed Poincaré inequality$\text{dist}_{2}^{\text{mono}}(f)^{2}\leq C\mathbb{E}\Vert \nabla^{-}f\vert^{2}]$, where the “directed gradient” operator$\nabla{-}$measures the local violations of monotonicity of$f$. To prove the second result, we introduce a partial differential equation (PDE), the directed heat equation, which takes a one-dimensional function$f$into a monotone function$f^{*}$over time and enjoys many desirable analytic properties. We obtain the directed Poincaré inequality by combining convergence aspects of this PDE with the theory of optimal transport. Crucially for our conceptual motivation, this proof is in complete analogy with the mathematical physics perspective on the classical Poincaré inequality, namely as characterizing the convergence of the standard heat equation toward equilibrium.

We are interested in testing properties of distributions with systematically mislabeled samples. Our goal is to make decisions about unknown probability distributions, using a sample that has been collected by a confused collector, such as a machine-learning classifier that has not learned to distinguish all elements of the domain. The confused collector holds an unknown clustering of the domain and an input distribution μ, and provides two oracles: a sample oracle which produces a sample from μ that has been labeled according to the clustering; and a label-query oracle which returns the label of a query point x according to the clustering. Our first set of results shows that identity, uniformity, and equivalence of distributions can be tested efficiently, under the earth-mover distance, with remarkably weak conditions on the confused collector, even when the unknown clustering is adversarial. This requires defining a variant of the distribution testing task (inspired by the recent testable learning framework of Rubinfeld & Vasilyan), where the algorithm should test a joint property of the distribution and its clustering. As an example, we get efficient testers when the distribution tester is allowed to reject if it detects that the confused collector clustering is "far" from being a decision tree. The second set of results shows that we can sometimes do significantly better when the clustering is random instead of adversarial. For certain one-dimensional random clusterings, we show that uniformity can be tested under the TV distance using Õ((√n)/(ρ^{3/2} ε²)) samples and zero queries, where ρ ∈ (0,1] controls the "resolution" of the clustering. We improve this to O((√n)/(ρ ε²)) when queries are allowed.

We study the connection between directed isoperimetric inequalities and monotonicity testing. In recent years, this connection has unlocked breakthroughs for testing monotonicity of functions defined on discrete domains. Inspired the rich history of isoperimetric inequalities in continuous settings, we propose that studying the relationship between directed isoperimetry and monotonicity in such settings is essential for understanding the full scope of this connection. Hence, we ask whether directed isoperimetric inequalities hold for functions f:[0,1]ⁿ → R, and whether this question has implications for monotonicity testing. We answer both questions affirmatively. For Lipschitz functions f:[0,1]ⁿ → ℝ, we show the inequality d^mono₁(f) ≲ 𝔼 [‖∇^- f‖₁], which upper bounds the L¹ distance to monotonicity of f by a measure of its "directed gradient". A key ingredient in our proof is the monotone rearrangement of f, which generalizes the classical "sorting operator" to continuous settings. We use this inequality to give an L¹ monotonicity tester for Lipschitz functions f:[0,1]ⁿ → ℝ, and this framework also implies similar results for testing real-valued functions on the hypergrid.

We consider the problem of determining which classes of functions can be tested more efficiently than they can be learned, in the distribution-free sample-based model that corresponds to the standard PAC learning setting. Our main result shows that while VC dimension by itself does not always provide tight bounds on the number of samples required to test a class of functions in this model, it can be combined with a closely-related variant that we call “lower VC” (or LVC) dimension to obtain strong lower bounds on this sample complexity.

Jing Yi Xie, Renato Ferreira Pinto Junior, Graeme Hirst, Yang Xu. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.