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.
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.
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.
We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function f on N bits, define F(x_1,...,x_M) = OMB(f(x_1),...,f(x_M)) to be the function on M*N bits obtained by block-composing f with a function known as ODD-MAX-BIT. We show that, if f requires large degree to approximate to error 2/3 in a certain one-sided sense (captured by a complexity measure known as positive one-sided approximate degree), then F requires large degree to approximate even to error 1-2^{-M}. This generalizes a result of Beigel (Computational Complexity, 1994), who proved an identical result for the special case f=OR. Unlike related prior work, our result implies strong approximate degree lower bounds even for many functions F that have low threshold degree. Our proof is constructive: we exhibit a solution to the dual of an appropriate linear program capturing the approximate degree of any function. We describe several applications, including improved separations between the complexity classes P^{NP} and PP in both the query and communication complexity settings. Our separations improve on work of Beigel (1994) and Buhrman, Vereshchagin, and de Wolf (CCC, 2007).
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 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.
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.
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.