The relative-error property testing model was introduced in [Chen et al., 2024] to facilitate the study of property testing for "sparse" Boolean-valued functions, i.e. ones for which only a small fraction of all input assignments satisfy the function. In this framework, the distance from the unknown target function f that is being tested to a function g is defined as Vol(f△g)/Vol(f), where the numerator is the fraction of inputs on which f and g disagree and the denominator is the fraction of inputs that satisfy f. Recent work [Chen et al., 2026] has shown that over the Boolean domain {0,1}ⁿ, any relative-error testing algorithm for the fundamental class of {halfspaces} (i.e. linear threshold functions) must make Ω(log n) oracle calls. In this paper we complement the [Chen et al., 2026] lower bound by showing that halfspaces can be relative-error tested over ℝⁿ under the standard N(0,I_n) Gaussian distribution using a sublinear number of oracle calls - in particular, substantially fewer than would be required for learning. Our results use a wide range of tools including Hermite analysis, Gaussian isoperimetric inequalities, and geometric results on noise sensitivity and surface area.

Several recent works (Chen et al., SODA 2025; Chen et al., ICALP 2025; Chen et al., COLT 2025; Chen et al., manuscript) have studied a model of property testing of Boolean functions under a relative-error criterion. In this model, the distance from a target function \(f : \{0, 1\}^n \rightarrow \{0, 1\}\) that is being tested to a function \(g\) is defined relative to the number of inputs \(x\) for which \(f(x) = 1\); moreover, testing algorithms in this model have access both to a black-box oracle for \(f\) and to independent uniform satisfying assignments of \(f\). The motivation for this model is that it provides a natural framework for testing sparse Boolean functions that have few satisfying assignments, analogous to well-studied models for property testing of sparse graphs.

We consider the problem of testing if an unknown low-degree polynomial p over ℝn is sparse versus far from sparse, given access to noisy evaluations of the polynomial p at randomly chosen points. This is a natural property-testing version of various well-studied problems about learning low-degree sparse polynomials in the presence of noise, and is a generalization of the work of Chen, De, and Servedio (2020), on testing noisy linear functions for sparsity, to the more challenging setting of low-degree polynomials.

We give a dimension-independent sparsification result for suprema of centered Gaussian processes: Let $T$ be any (possibly infinite) bounded set of vectors in $\mathbb{R}^n$, and let $\{\boldsymbol{X}_t := t \cdot \boldsymbol{g} \}_{t\in T}$ be the canonical Gaussian process on $T$, where $\boldsymbol{g}\sim N(0, I_n)$. We show that there is an $O_\varepsilon(1)$-size subset $S \subseteq T$ and a set of real values $\{c_s\}_{s \in S}$ such that the random variable $\sup_{s \in S} \{\boldsymbol{X}_s + c_s\}$ is an $\varepsilon$-approximator\,(in $L^1$) of the random variable $\sup_{t \in T} {\boldsymbol{X}}_t$. Notably, the size of the sparsifier $S$ is completely independent of both $|T|$ and the ambient dimension $n$. We give two applications of this sparsification theorem: - A "Junta Theorem" for Norms: We show that given any norm $ν(x)$ on $\mathbb{R}^n$, there is another norm $ψ(x)$ depending only on the projection of $x$ onto $O_\varepsilon(1)$ directions, for which $ψ({\boldsymbol{g}})$ is a multiplicative $(1 \pm \varepsilon)$-approximation of $ν({\boldsymbol{g}})$ with probability $1-\varepsilon$ for ${\boldsymbol{g}} \sim N(0,I_n)$. - Sparsification of Convex Sets: We show that any intersection of (possibly infinitely many) halfspaces in $\mathbb{R}^n$ that are at distance $r$ from the origin is $\varepsilon$-close (under $N(0,I_n)$) to an intersection of only $O_{r,\varepsilon}(1)$ halfspaces. This yields new polynomial-time \emph{agnostic learning} and \emph{tolerant property testing} algorithms for intersections of halfspaces.

A subset S of the Boolean hypercube 𝔽₂ⁿ is a sumset if S = {a + b : a, b ∈ A} for some A ⊆ 𝔽₂ⁿ. Sumsets are central objects of study in additive combinatorics, where they play a role in several of the field’s most important results. We prove a lower bound of Ω(2^{n/2}) for the number of queries needed to test whether a Boolean function f:𝔽₂ⁿ → {0,1} is the indicator function of a sumset, ruling out an efficient testing algorithm for sumsets. Our lower bound for testing sumsets follows from sharp bounds on the related problem of shift testing, which may be of independent interest. We also give a near-optimal {2^{n/2} ⋅ poly(n)}-query algorithm for a smoothed analysis formulation of the sumset refutation problem. Finally, we include a simple proof that the number of different sumsets in 𝔽₂ⁿ is 2^{(1±o(1))2^{n-1}}.

In 1992 Blum and Rudich [1] gave an algorithm that uses membership and equivalence queries to learn k-term DNF formulas over $\{0,1\}^{n}$ in time $\operatorname{poly}\left(n, 2^{k}\right)$, improving on the naive $O\left(n^{k}\right)$ running time that can be achieved without membership queries [2]. Since then, many alternative algorithms [3]–[6] have been given which also achieve runtime poly $\left(n, 2^{k}\right)$. We give an algorithm that uses membership and equivalence queries to learn k-term DNF formulas in time poly $(n) \cdot 2^{\tilde{O}(\sqrt{k})}$. This is the first improvement for this problem since the original work of Blum and Rudich [1]. Our approach employs the Winnow2 algorithm for learning linear threshold functions over an enhanced feature space which is adaptively constructed using membership queries. It combines a strengthened version of a technique that effectively reduces the length of DNF terms from the original work of [1] with a range of additional algorithmic tools (attribute-efficient learning algorithms for low-weight linear threshold functions and techniques for finding relevant variables from junta testing) and analytic ingredients (extremal polynomials and noise operators) that are novel in the context of query-based DNF learning.

The standard model of Boolean function property testing is not well suited for testing sparse functions which have few satisfying assignments, since every such function is close (in the usual Hamming distance metric) to the constant-0 function. In this work we propose and investigate a new model for property testing of Boolean functions, called relative-error testing, which provides a natural framework for testing sparse functions.

We consider the problem of testing whether an unknown and arbitrary set S ⊆ ℝn (given as a black-box membership oracle) is convex, versus ε-far from every convex set, under the standard Gaussian distribution.

STOC ’25, Prague, Czechia

We study the approximability of general convex sets in$\mathbb{R}^{n}$by intersections of halfspaces, where the approximation quality is measured with respect to the standard Gaussian distribution and the complexity of an approximation is the number of halfspaces used. While a large body of research has considered the approximation of convex sets by intersections of halfspaces under distance metrics such as the Lebesgue measure and Hausdorff distance, prior to our work there has not been a systematic study of convex approximation under the Gaussian distribution. We establish a range of upper and lower bounds, both for general convex sets and for specific natural convex sets that are of particular interest. Our results demonstrate that the landscape of approximation is intriguingly different under the Gaussian distribution versus previously studied distance measures. Our results are proved using techniques from many different areas. These include classical results on convex polyhedral approximation, Cramér-type bounds on large deviations from probability theory, and-perhaps surprisingly-a range of topics from computational complexity, including computational learning theory, unconditional pseudorandomness, and the study of influences and noise sensitivity in the analysis of Boolean functions.

Inspired by the classic problem of Boolean function monotonicity testing, we investigate the testability of other well-studied properties of combinatorial finite set systems, specifically \emph{intersecting} families and \emph{union-closed} families. A function $f: \{0,1\}^n \to \{0,1\}$ is intersecting (respectively, union-closed) if its set of satisfying assignments corresponds to an intersecting family (respectively, a union-closed 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 union-closed set system, both turn out to be information-theoretically difficult to test. We show that: $\bullet$ For $ε\geq Ω(1/\sqrt{n})$, any non-adaptive two-sided $ε$-tester for intersectingness must make $2^{Ω(n^{1/4}/\sqrtε)}$ queries. We also give a $2^{Ω(\sqrt{n \log(1/ε)})}$-query lower bound for non-adaptive one-sided $ε$-testers for intersectingness. $\bullet$ For $ε\geq 1/2^{Ω(n^{0.49})}$, any non-adaptive two-sided $ε$-tester for union-closedness must make $n^{Ω(\log(1/ε))}$ queries. Thus, neither intersectingness nor union-closedness shares the $\mathrm{poly}(n,1/ε)$-query non-adaptive testability that is enjoyed by monotonicity. To complement our lower bounds, we also give a simple $\mathrm{poly}(n^{\sqrt{n\log(1/ε)}},1/ε)$-query, one-sided, non-adaptive algorithm for $ε$-testing each of these properties (intersectingness and union-closedness). We thus achieve nearly tight upper and lower bounds for two-sided testing of intersectingness when $ε= Θ(1/\sqrt{n})$, and for one-sided testing of intersectingness when $ε=Θ(1).$

We give the first super-polynomial (in fact, mildly exponential) lower bounds for tolerant testing (equivalently, distance estimation) of monotonicity, unateness, and juntas with a constant separation between the “yes” and “no” cases. Specifically, we give

We consider the following basic, and very broad, statistical problem: Given a known high-dimensional distribution D over ℝn and a collection of data points in ℝn, distinguish between the two possibilities that (i) the data was drawn from D, versus (ii) the data was drawn from D|S, i.e. from D subject to truncation by an unknown truncation set S ⊆ ℝn. We study this problem in the setting where D is a high-dimensional i.i.d. product distribution and S is an unknown degree-d polynomial threshold function (one of the most well-studied types of Boolean-valued function over ℝn). Our main results are an efficient algorithm when D is a hypercontractive distribution, and a matching lower bound: 1. For any constant d, we give a polynomial-time algorithm which successfully distinguishes D from D|S using O(nd/2) samples (subject to mild technical conditions on D and S); 2. Even for the simplest case of D being the uniform distribution over {±1}n, we show that for any constant d, any distinguishing algorithm for degree-d polynomial threshold functions must use Ω(nd/2) samples.

We give a non-adaptive algorithm that makes 2O(√klog(1/ε2 − ε1)) queries to a Boolean function f:{±1}n→{±1} and distinguishes between f being ε1-close to some k-junta versus ε2-far from every k-junta. At the heart of our algorithm is a local mean estimation procedure for Boolean functions that may be of independent interest. We complement our upper bound with a matching lower bound, improving a recent lower bound obtained by Chen et al. We thus obtain the first tight bounds for a natural property of Boolean functions in the tolerant testing model.

The circuit class QAC0 was introduced by Moore (1999) as a model for constant depth quantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower bounds against such circuits is a longstanding challenge in quantum circuit complexity; in particular, showing that polynomial-size QAC0 cannot compute the parity function has remained an open question for over 20 years. In this work, we identify a notion of the Pauli spectrum of QAC0 circuits, which can be viewed as the quantum analogue of the Fourier spectrum of classical AC0 circuits. We conjecture that the Pauli spectrum of QAC0 circuits satisfies low-degree concentration, in analogy to the famous Linial, Mansour, Nisan (LMN) theorem on the low-degree Fourier concentration of AC0 circuits. If true, this conjecture immediately implies that polynomial-size QAC0 circuits cannot compute parity. We prove this conjecture for the class of depth-d, polynomial-size QAC0 circuits with at most nO(1/d) auxiliary qubits. We obtain new circuit lower bounds and learning results as applications: this class of circuits cannot correctly compute the n-bit parity function on more than (1/2 + 2−Ω(n1/d))-fraction of inputs, and the n-bit majority function on more than (1/2 + O(n−1/4))-fraction of inputs. Additionally we show that this class of QAC0 circuits with limited auxiliary qubits can be learned with quasipolynomial sample complexity, giving the first learning result for QAC0 circuits. More broadly, our results add evidence that “Pauli-analytic” techniques can be a powerful tool in studying quantum circuits.

We consider the problem of testing and learning quantum k-juntas: n-qubit unitary matrices which act non-trivially on just k of the n qubits and as the identity on the rest. As our main algorithmic results, we give 1. A -query quantum algorithm that can distinguish quantum k-juntas from unitary matrices that are “far” from every quantum k-junta; and 2. A O(4k)-query algorithm to learn quantum k-juntas. We complement our upper bounds for testing and learning quantum k-juntas with near-matching lower bounds of and Ω(4k/k), respectively. Our techniques are Fourier-analytic and make use of a notion of influence of qubits on unitaries. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.05898

We study the basic statistical problem of testing whether normally distributed n-dimensional data has been truncated, i.e. altered by only retaining points that lie in some unknown truncation set S ⊆ ℝn. As our main algorithmic results 1. We give a computationally efficient O(n)-sample algorithm that can distinguish the standard normal distribution N(0,In) from N(0,In) conditioned on an unknown and arbitrary convex set S. 2. We give a different computationally efficient O(n)-sample algorithm that can distinguish N(0,In) from N(0,In) conditioned on an unknown and arbitrary mixture of symmetric convex sets. These results stand in sharp contrast with known results for learning or testing convex bodies with respect to the normal distribution or learning convex-truncated normal distributions, where state-of-the-art algorithms require essentially samples. An easy argument shows that no finite number of samples suffices to distinguish N(0,In) from an unknown and arbitrary mixture of general (not necessarily symmetric) convex sets, so no common generalization of results (1) and (2) above is possible. We also prove lower bounds on the sample complexity of distinguishing algorithms (computationally efficient or otherwise) for various classes of convex truncations; in some cases these lower bounds match our algorithms up to logarithmic or even constant factors.

We introduce a new notion of influence for symmetric convex sets over Gaussian space, which we term "convex influence". We show that this new notion of influence shares many of the familiar properties of influences of variables for monotone Boolean functions $f: \{\pm1\}^n \to \{\pm1\}.$ Our main results for convex influences give Gaussian space analogues of many important results on influences for monotone Boolean functions. These include (robust) characterizations of extremal functions, the Poincaré inequality, the Kahn-Kalai-Linial theorem, a sharp threshold theorem of Kalai, a stability version of the Kruskal-Katona theorem due to O'Donnell and Wimmer, and some partial results towards a Gaussian space analogue of Friedgut's junta theorem. The proofs of our results for convex influences use very different techniques than the analogous proofs for Boolean influences over $\{\pm1\}^n$. Taken as a whole, our results extend the emerging analogy between symmetric convex sets in Gaussian space and monotone Boolean functions from $\{\pm1\}^n$ to $\{\pm1\}$

Given a subset A of the n-dimensional Boolean hypercube , the sumset A+A is the set {a + a′ : a, a′ ∊ A} where addition is in . Sumsets play an important role in additive combinatorics, where they feature in many central results of the field. The main result of this paper is a sublinear-time algorithm for the problem of sumset size estimation. In more detail, our algorithm is given oracle access to (the indicator function of) an arbitrary and an accuracy parameter ∊ > 0, and with high probability it outputs a value 0 ≤ v ≤ 1 that is ±∊-close to Vol (A′ + A′) for some perturbation A′ ⊆ A of A satisfying Vol (A \ A′) ≤ ∊. It is easy to see that without the relaxation of dealing with A′ rather than A, any algorithm for estimating Vol (A + A) to any nontrivial accuracy must make 2Ω(n) queries. In contrast, we give an algorithm whose query complexity depends only on ∊ and is completely independent of the ambient dimension n.

Most correlation inequalities for high-dimensional functions in the literature, such as the Fortuin-Kasteleyn-Ginibre inequality and the celebrated Gaussian Correlation Inequality of Royen, are qualitative statements which establish that any two functions of a certain type have non-negative correlation. We give a general approach that can be used to bootstrap many qualitative correlation inequalities for functions over product spaces into quantitative statements. The approach combines a new extremal result about power series, proved using complex analysis, with harmonic analysis of functions over product spaces. We instantiate this general approach in several different concrete settings to obtain a range of new and near-optimal quantitative correlation inequalities, including: - A {quantitative} version of Royen’s celebrated Gaussian Correlation Inequality [Royen, 2014]. In [Royen, 2014] Royen confirmed a conjecture, open for 40 years, stating that any two symmetric convex sets must be non-negatively correlated under any centered Gaussian distribution. We give a lower bound on the correlation in terms of the vector of degree-2 Hermite coefficients of the two convex sets, conceptually similar to Talagrand’s quantitative correlation bound for monotone Boolean functions over {0,1}ⁿ [M. Talagrand, 1996]. We show that our quantitative version of Royen’s theorem is within a logarithmic factor of being optimal. - A quantitative version of the well-known FKG inequality for monotone functions over any finite product probability space. This is a broad generalization of Talagrand’s quantitative correlation bound for functions from {0,1}ⁿ to {0,1} under the uniform distribution [M. Talagrand, 1996]; the only prior generalization of which we are aware is due to Keller [Nathan Keller, 2012; Keller, 2008; Nathan Keller, 2009], which extended [M. Talagrand, 1996] to product distributions over {0,1}ⁿ. In the special case of p-biased distributions over {0,1}ⁿ that was considered by Keller, our new bound essentially saves a factor of p log(1/p) over the quantitative bounds given in [Nathan Keller, 2012; Keller, 2008; Nathan Keller, 2009]. We also give {a quantitative version of} the FKG inequality for monotone functions over the continuous domain [0,1]ⁿ, answering a question of Keller [Nathan Keller, 2009].