Eric Blais

FOCS Conference 2025 Conference Paper

Direct Product Theorems for Randomized Query Complexity

• Shalev Ben-David
• Eric Blais

We establish two new direct product theorems for the randomized query complexity of Boolean functions. The first shows that computing n copies of a function f, even with a small success probability of $\gamma^{n}$, requires $\Theta(n)$ times the maximum distributional query complexity of f with success parameter $\gamma$. This result holds for all success parameters $\gamma$, even when $\gamma$ is very close to 1/2 or to 1. As a result, it unifies and generalizes Drucker’s direct product theorem (2012) for $\gamma$ bounded away from $\frac{1}{2}$ and 1 as well as the strong direct sum theorem of Blais and Brody (2019) for $\gamma \approx 1-1 / n$. The second establishes a general list decoding direct product theorem that captures many different variants of “partial computation” tasks related to the function $f^{n}$ consisting of n copies of f. Notably, our list decoding direct product theorem yields a new threshold direct product theorem and other new variants such as the labelled-threshold direct product theorem. Both of these direct product theorems are obtained by taking a new approach. Instead of directly analyzing the query complexity of algorithms, we introduce a new measure of complexity of functions that we call discounted score. We show that this measure satisfies a number of useful structural properties, including tensorization, that make it particularly suitable for the study of direct product questions.

STOC Conference 2024 Conference Paper

New Graph and Hypergraph Container Lemmas with Applications in Property Testing

• Eric Blais
• Cameron Seth

FOCS Conference 2023 Conference Paper

Testing Graph Properties with the Container Method

• Eric Blais
• Cameron Seth

We establish nearly optimal sample complexity bounds for testing the $\rho$-clique property in the dense graph model. Specifically, we show that it is possible to distinguish graphs on n vertices that have a $\rho n$-clique from graphs for which at least $\epsilon n^{2}$ edges must be added to form a $\rho n$-clique by sampling and inspecting a random subgraph on only $\tilde{O}\left(\rho^{3} / \epsilon^{2}\right)$ vertices. We also establish new sample complexity bounds for $\epsilon$-testing k-colorability. In this case, we show that a sampled subgraph on $\tilde{O}(k / \epsilon)$ vertices suffices to distinguish k-colorable graphs from those for which any k-coloring of the vertices causes at least $\epsilon n^{2}$ edges to be monochromatic. The new bounds for testing the $\rho$-clique and k-colorability properties are both obtained via new extensions of the graph container method. This method has been an effective tool for tackling various problems in graph theory and combinatorics. Our results demonstrate that it is also a powerful tool for the analysis of property testing algorithms.

FOCS Conference 2022 Conference Paper

Randomised Composition and Small-Bias Minimax

• Shalev Ben-David
• Eric Blais
• Mika Göös
• Gilbert Maystre

We prove 1 two results about randomised query complexity $\mathbf{R}(f)$. First, we introduce a linearised complexity measure LR and show that it satisfies an inner-optimal composition theorem: $\mathbf{R}(f^{\circ} g)\geq\Omega(\mathbf{R}(f)\mathbf{L R}(g))$ for all partial f and g, and moreover, LR is the largest possible measure with this property. In particular, LR can be polynomially larger than previous measures that satisfy an inner composition theorem, such as the max-conflict complexity of Gavinsky, Lee, Santha, and Sanyal (ICALP 2019). Our second result addresses a question of Yao (FOCS 1977). He asked if $\epsilon$-error expected query complexity $\overline{\mathbf{R}}_{\epsilon}(f)$ admits a distributional characterisation relative to some hard input distribution. Vereshchagin (TCS 1998) answered this question affirmatively in the bounded-error case. We show that an analogous theorem fails in the small-bias case $\epsilon=1/2-o(1)$. 1 This is an extended abstract. For the full version of this article, please refer to [BDBGM22].

STOC Conference 2021 Conference Paper

VC dimension and distribution-free sample-based testing

• Eric Blais
• Renato Ferreira Pinto Jr.
• Nathaniel Harms

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. We use this result to obtain strong and in many cases nearly optimal bounds on the sample complexity for testing unions of intervals, halfspaces, intersections of halfspaces, polynomial threshold functions, and decision trees. Conversely, we show that two natural classes of functions, juntas and monotone functions, can be tested with a number of samples that is polynomially smaller than the number of samples required for PAC learning. Finally, we also use the connection between VC dimension and property testing to establish new lower bounds for testing radius clusterability and testing feasibility of linear constraint systems.

FOCS Conference 2020 Conference Paper

A New Minimax Theorem for Randomized Algorithms (Extended Abstract)

• Shalev Ben-David
• Eric Blais

The celebrated minimax principle of Yao (1977) says that for any Boolean-valued function f with finite domain, there is a distribution μ over the domain of f such that computing f to error ε against inputs from μ is just as hard as computing f to error ε on worst-case inputs. Notably, however, the distribution μ depends on the target error level ε: the hard distribution which is tight for bounded error might be trivial to solve to small bias, and the hard distribution which is tight for a small bias level might be far from tight for bounded error levels. In this work, we introduce a new type of minimax theorem which can provide a hard distribution μ that works for all bias levels at once. We show that this works for randomized query complexity, randomized communication complexity, some randomized circuit models, quantum query and communication complexities, approximate polynomial degree, and approximate logrank. We also prove an improved version of Impagliazzo's hardcore lemma. Our proofs rely on two innovations over the classical approach of using Von Neumann's minimax theorem or linear programming duality. First, we use Sion's minimax theorem to prove a minimax theorem for ratios of bilinear functions representing the cost and score of algorithms. Second, we introduce a new way to analyze low-bias randomized algorithms by viewing them as “forecasting algorithms” evaluated by a certain proper scoring rule. The expected score of the forecasting version of a randomized algorithm appears to be a more fine-grained way of analyzing the bias of the algorithm. We show that such expected scores have many elegant mathematical properties: for example, they can be amplified linearly instead of quadratically. We anticipate forecasting algorithms will find use in future work in which a fine-grained analysis of small-bias algorithms is required.

FOCS Conference 2020 Conference Paper

A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions: Extended Abstract

• Shalev Ben-David
• Eric Blais

We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions f and g such that R(f°g) ≪ R(f)R(g). In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of f). Second, we show that for all f and g, R(f°g) = Ω(noisyR(f) R(g)), where noisyR(f) is a measure describing the cost of computing f on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure M(·) satisfying R(f°g)=Ω(M(f)R(g)) for all f and g, it must hold that noisyR(f)=Ω(M(f)) for all f. We also give a clean characterization of the measure noisyR(f): it satisfies noisyR(f)=Θ(R(f°GapMajn)/R(GapMajn)), where n is the input size of f and GapMajn is the √n-gap majority function on n bits.

SODA Conference 2020 Conference Paper

Testing convexity of functions over finite domains

• Aleksandrs Belovs
• Eric Blais
• Abhinav Bommireddi

We establish new upper and lower bounds on the number of queries required to test convexity of functions over various discrete domains. We provide a simplified version of the non-adaptive convexity tester on the line. We re-prove the upper bound in the usual uniform model, and prove an upper bound in the distribution-free setting. We show a tight lower bound of queries for testing convexity of functions f: [ n ] → ℝ on the line. This lower bound applies to both adaptive and non-adaptive algorithms, and matches the upper bound from item 1, showing that adaptivity does not help in this setting. Moving to higher dimensions, we consider the case of a stripe [3] × [ n ]. We construct an adaptive tester for convexity of functions f: [3] × [ n ] → ℝ with query complexity O (log 2 n ). We also show that any non-adaptive tester must use queries in this setting. Thus, adaptivity yields an exponential improvement for this problem. For functions f: [ n ] d → ℝ over domains of dimension d ≥ 2, we show a non-adaptive query lower bound.

SODA Conference 2018 Conference Paper

Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

• Eric Blais
• Clément L. Canonne
• Talya Eden
• Amit Levi
• Dana Ron

The function f: { – 1, 1} n → {– 1, 1} is a k -junta if it depends on at most k of its variables. We consider the problem of tolerant testing of k -juntas, where the testing algorithm must accept any function that is ∊-close to some k -junta and reject any function that is e ′-far from every k ′-junta for some ∊ ′ = O ( ∊ ) and k ′ = O ( k ). Our first result is an algorithm that solves this problem with query complexity polynomial in k and 1/ ∊. This result is obtained via a new polynomial-time approximation algorithm for submodular function minimization (SFM) under large cardinality constraints, which holds even when only given an approximate oracle access to the function. Our second result considers the case where k′ = k. We show how to obtain a smooth tradeoff between the amount of tolerance and the query complexity in this setting. Specifically, we design an algorithm that given ρ ∊ (0, 1/2) accepts any function that is -close to some k -junta and rejects any function that is ∊ -far from every k -junta. The query complexity of the algorithm is. Finally, we show how to apply the second result to the problem of tolerant isomorphism testing between two unknown Boolean functions f and g. We give an algorithm for this problem whose query complexity only depends on the (unknown) smallest k such that either f or g is close to being a k -junta.

STOC Conference 2016 Conference Paper

A polynomial lower bound for testing monotonicity

• Aleksandrs Belovs
• Eric Blais

We show that every algorithm for testing n -variate Boolean functions for monotonicityhas query complexity Ω( n 1/4 ). All previous lower bounds for this problem were designed for non-adaptive algorithms and, as a result, the best previous lower bound for general (possibly adaptive) monotonicity testers was only Ω(log n ). Combined with the query complexity of the non-adaptive monotonicity tester of Khot, Minzer, and Safra (FOCS 2015), our lower bound shows that adaptivity can result in at most a quadratic reduction in the query complexity for testing monotonicity. By contrast, we show that there is an exponential gap between the query complexity of adaptive and non-adaptive algorithms for testing regular linear threshold functions (LTFs) for monotonicity. Chen, De, Servedio, and Tan (STOC 2015)recently showed that non-adaptive algorithms require almost Ω( n 1/2 ) queries for this task. We introduce a new adaptive monotonicity testing algorithm which has query complexity O (log n ) when the input is a regular LTF.

FOCS Conference 2012 Conference Paper

Active Property Testing

• Maria-Florina Balcan
• Eric Blais
• Avrim Blum
• Liu Yang 0001

One motivation for property testing of boolean functions is the idea that testing can provide a fast preprocessing step before learning. However, in most machine learning applications, it is not possible to request for labels of arbitrary examples constructed by an algorithm. Instead, the dominant query paradigm in applied machine learning, called active learning, is one where the algorithm may query for labels, but only on points in a given (polynomial-sized) unlabeled sample, drawn from some underlying distribution D. In this work, we bring this well-studied model to the domain of testing. We develop both general results for this active testing model as well as efficient testing algorithms for several important properties for learning, demonstrating that testing can still yield substantial benefits in this restricted setting. For example, we show that testing unions of d intervals can be done with O(1) label requests in our setting, whereas it is known to √ require Ω(d) labeled examples for learning (and Ω(√d) for passive testing [22] where the algorithm must pay for every example drawn from D). In fact, our results for testing unions of intervals also yield improvements on prior work in both the classic query model (where any point in the domain can be queried) and the passive testing model as well. For the problem of testing linear separators in Rn over the Gaussian distribution, we show that both active and passive testing can be done with O(√n) queries, substantially less than the Ω(n) needed for learning, with near-matching lower bounds. We also present a general combination result in this model for building testable properties out of others, which we then use to provide testers for a number of assumptions used in semi-supervised learning. In addition to the above results, we also develop a general notion of the testing dimension of a given property with respect to a given distribution, that we show characterizes (up to constant factors) the intrinsic number of label requests needed to test that property. We develop such notions for both the active and passive testing models. We then use these dimensions to prove a number of lower bounds, including for linear separators and the class of dictator functions.

FOCS Conference 2012 Conference Paper

Partially Symmetric Functions Are Efficiently Isomorphism-Testable

• Eric Blais
• Amit Weinstein
• Yuichi Yoshida

Given a Boolean function f, the f-isomorphism testing problem requires a randomized algorithm to distinguish functions that are identical to f up to relabeling of the input variables from functions that are far from being so. An important open question in property testing is to determine for which functions f we can test f-isomorphism with a constant number of queries. Despite much recent attention to this question, essentially only two classes of functions were known to be efficiently isomorphism testable: symmetric functions and juntas. We unify and extend these results by showing that all partially symmetric functions -- functions invariant to the reordering of all but a constant number of their variables -- are efficiently isomorphism-testable. This class of functions, first introduced by Shannon, includes symmetric functions, juntas, and many other functions as well. We conjecture that these functions are essentially the only functions efficiently isomorphism-testable. To prove our main result, we also show that partial symmetry is efficiently testable. In turn, to prove this result we had to revisit the junta testing problem. We provide a new proof of correctness of the nearly-optimal junta tester. Our new proof replaces the Fourier machinery of the original proof with a purely combinatorial argument that exploits the connection between sets of variables with low influence and intersecting families. Another important ingredient in our proofs is a new notion of symmetric influence. We use this measure of influence to prove that partial symmetry is efficiently testable and also to construct an efficient sample extractor for partially symmetric functions. We then combine the sample extractor with the testing-by-implicit-learning approach to complete the proof that partially symmetric functions are efficiently isomorphism-testable.

STOC Conference 2009 Conference Paper

Testing juntas nearly optimally

• Eric Blais

A function on n variables is called a k-junta if it depends on at most k of its variables. In this article, we show that it is possible to test whether a function is a k-junta or is "far" from being a k-junta with O(kε + k log k ) queries, where epsilon is the approximation parameter. This result improves on the previous best upper bound of O (k 3/2 )ε queries and is asymptotically optimal, up to a logarithmic factor. We obtain the improved upper bound by introducing a new algorithm with one-sided error for testing juntas. Notably, the algorithm is a valid junta tester under very general conditions: it holds for functions with arbitrary finite domains and ranges, and it holds under any product distribution over the domain. A key component of the analysis of the new algorithm is a new structural result on juntas: roughly, we show that if a function f is "far" from being a k-junta, then f is "far" from being determined by k parts in a random partition of the variables. The structural lemma is proved using the Efron-Stein decomposition method.