A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions $f:\{0,1\}^n\to\{0,1\}$ and $g:\{0,1\}^m\to\{0,1\}$, \[ \widetilde{deg}(f\circ g) = Θ\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), \] where $\widetilde{deg}$ denotes constant-error approximate degree.
We also consider the analogous question for exact quantum query complexity and give a counterexample showing that multiplicative composition fails in this setting.
Comments
Added a counterexample to multiplicative composition for exact quantum query complexity
A longstanding open question in Boolean function complexity asks whether approximate degree composes multiplicatively under block composition. Although a general multiplicative upper bound is known, matching lower bounds have previously been established only for restricted classes of functions. We resolve this question for all total Boolean functions by proving the matching lower bound. Together with Sherstov's upper bound, our result shows that, for every pair of total Boolean functions f:{0,1}n→{0,1} and g:{0,1}m→{0,1}, [ \widetilde{deg}(f\circ g) = Θ!\left( \widetilde{deg}(f),\widetilde{deg}(g) \right), ] where deg denotes constant-error approximate degree.
We also consider the analogous question for exact quantum query complexity and give a counterexample showing that multiplicative composition fails in this setting.
For any Boolean functions f and g, the question whether R(f∘g)=Θ~(R(f)⋅R(g)) is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether deg(f∘g)=Θ~(deg(f)⋅deg(g)) . These questions are two of the most important and well-studied problems in the field of analysis of Boolean functions, and yet we are far from answering them satisfactorily. It is known that the measures compose if one assumes various properties of the outer function f (or inner function g). This paper extends the class of outer functions for which R and deg compose. A recent landmark result (Ben-David and Blais, 2020) showed that R(f∘g)=Ω(noisyR(f)⋅R(g)) . This implies that composition holds iff noisyR(f)=Θ~(R(f)) . We show two results: On the other hand, we prove that deg(f∘g)=Ω(bs(f)⋅deg(g)), where bs(f) is the block sensitivity of f. This implies that deg composes when deg(f) is asymptotically equal to bs(f) . It is already known that both R and deg compose when the outer function is symmetric. We also extend these results to weaker notions of symmetry with respect to the outer function.
Determining the approximate degree composition for Boolean functions remains a significant unsolved problem in Boolean function complexity. In recent decades, researchers have concentrated on proving that approximate degree composes for special types of inner and outer functions. An important and extensively studied class of functions are the recursive functions, i.e.~functions obtained by composing a base function with itself a number of times. Let hd denote the standard d-fold composition of the base function h. The main result of this work is to show that the approximate degree composes if either of the following conditions holds: (I) The outer function f:{0,1}n→{0,1} is a recursive function of the form hd, with h being any base function and d=Ω(loglogn). (II) The inner function is a recursive function of the form hd, with h being any constant arity base function (other than AND and OR) and d=Ω(loglogn), where n is the arity of the outer function. In terms of proof techniques, we first observe that the lower bound for composition can be obtained by introducing majority in between the inner and the outer functions. We then show that majority can be \emph{efficiently eliminated} if the inner or outer function is a recursive function.
We introduce the subcube stifling number, a new combinatorial measure of total Boolean functions. This measure is the largest integer k such that, for every set S of at most k input variables and every assignment b∈{0,1}S, there is a fixing of the variables outside S under which the resulting function on the free variables S is the point indicator I[xS=b]. Equivalently, for every small set of coordinates, the function can isolate any prescribed point of the corresponding Boolean cube by suitably fixing all remaining coordinates. This measure is inspired by the stifling number of Chattopadhyay et al.~(ITCS'23); whereas their measure asks for restrictions realizing every constant function, ours asks for restrictions realizing every point indicator. Our results are as follows. 1) We show that the subcube stifling number gives rise to an approximate-degree composition theorem. In particular, if a Boolean function f has approximate degree O(μ(f)), then for every Boolean function g, approximate degree composes tightly. This motivates the study of the subcube stifling number, and in particular the search for functions whose approximate degree is O(μ(f)). 2) We show that a random Boolean function on n input bits has subcube stifling number Θ(log(n)) with high probability. 3) We show that indicators of linear codes over F2 whose minimum distance and dual distance are both linear have high subcube stifling number. 4) We prove that the functions arising from this linear-code construction do not have approximate degree O(μ(f)); in fact, they have approximate degree Ω(μ(f)). The main question left open is whether there exists a Boolean function f with approximate degree Θ(μ(f)). A positive answer would yield new instances of tight approximate-degree composition.
We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove these lower bounds using a quantum query algorithm for the combinatorial group testing problem. We show that for any function f, the approximate degree of computing the OR of n copies of f is Omega(sqrt n) times the approximate degree of f, which is optimal. No such general result was known prior to our work, and even the lower bound for the OR of ANDs function was only resolved in 2013. We then prove an analogous result in communication complexity, showing that the logarithm of the approximate rank (or more precisely, the approximate gamma-2 norm) of F: X x Y to 0,1 grows by a factor of Omega (sqrtn) when we take the OR of n copies of F, which is also essentially optimal. As a corollary, we give a new proof of Razborov's celebrated Omega(sqrtn) lower bound on the quantum communication complexity of the disjointness problem. Finally, we generalize both these results from composition with the OR function to composition with arbitrary symmetric functions, yielding nearly optimal lower bounds in this setting as well.
The approximate degree of a Boolean function f(x1,x2,…,xn) is the minimum degree of a real polynomial that approximates f pointwise within 1/3. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a first-principles, classical approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: - O(n43−4(2k−1)1) for the k-element distinctness problem; - O(n1−k+11) for the k-subset sum problem; - O(n1−k+11) for any k-DNF or k-CNF formula; - O(n3/4) for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the Θ(n) quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree Ω(n). In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.
The approximate non-deterministic degree of a Boolean function f, denoted ndegε(f) (written Nε(f) for brevity), is the minimum degree of a real polynomial p such that 0≤∣p(x)∣≤ε whenever f(x)=0, and ∣p(x)∣≥1 whenever f(x)=1. Unlike exact non-deterministic degree, which only requires the polynomial to be nonzero on 1-inputs, this measure enforces a uniform gap: the polynomial must stay close to zero on all 0-inputs and bounded away from zero on all 1-inputs.
The rational degree conjecture, open for over three decades, was recently resolved by Kothari, Kovacs-Deak, Wang, and Yang, who showed that for every total Boolean function f, deg(f)≤O(rdeg(f)3).
In their paper, they explicitly propose a stronger conjecture: that approximate degree is polynomially bounded by Nε(f) and Nε(f) jointly, i.e., for every total Boolean function f and every constant 0<ε<1, deg(f)≤poly(Nε(f),Nε(f)).
This conjecture, if true, would imply a polynomial version of the rational degree result and bring us closer to resolving de Wolf's longstanding non-deterministic degree conjecture.
In this work, we make the first systematic progress on this problem, establishing the conjecture for several broad and natural function classes: monotone and unate functions, functions of bounded alternation number, symmetric functions, k-uniform hypergraph properties, and read-k Disjunctive Normal Form (DNF) formulas.