PaperlayerView exact revision on arXiv

Source-linked AI summary

A General Composition Theorem for Approximate Degree

Samruddhi Pednekar, Supartha Podder

arXiv:2609.30139v1cs.CCquant-ph

TL;DR

Whether approximate degree composes multiplicatively for all total Boolean functions was open, with lower bounds known only for restricted classes. This paper proves the missing lower bound, matching the known upper bound and establishing multiplicative composition for every pair of total Boolean functions.

  • Problem

    Whether approximate degree composes multiplicatively for all total Boolean functions remained open, despite lower bounds for restricted classes.

    Source: §1 · p. 2

  • Method

    The proof starts from an approximant to the composition, averages it over blocks sampled according to prescribed inner-function outputs, and uses a dual-witness-based distribution for arbitrary inner functions.

    Source: §3 · pp. 6–7

  • Results

    For arbitrary total Boolean functions f and g, approximate degree of f ◦ g is Ω(approximate degree of f times approximate degree of g), matching the known upper-bound direction.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The matching lower and upper bounds establish multiplicative approximate-degree composition for every pair of total Boolean functions.

    Source: §1 · p. 3

    The proof uses bounded approximate degree: the approximant must work on the promise and remain bounded on the entire Boolean cube.

    Source: §3 · p. 7

Abstract

from arXiv · show

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) = \Theta\!\left( \widetilde{deg}(f)\,\widetilde{deg}(g) \right), \] where $\widetilde{deg}$ denotes constant-error approximate degree.

1 Introduction

The paper resolves the approximate-degree composition question for arbitrary total Boolean functions by proving the previously missing lower bound. Combined with the known upper bound, this gives multiplicative composition.

1 Introduction

  • The open question mattered because approximate degree is a central tool for proving lower bounds on quantum query complexity.The paper describes this complexity measure as well studied.Source: §1 · p. 2
  • Together with the upper bound proved in [31], the lower bound yields a multiplicative composition theorem for all total Boolean functions.[31] established the upper-bound direction.Source: §1 · pp. 2–3
  • Before this work, lower bounds for composition had been proved only for restricted classes, leaving arbitrary outer and inner functions unresolved.The introduction lists examples including linear-approximate-degree outer functions, symmetric outer functions, and recursive functions.Source: §1 · p. 2
  • For arbitrary total Boolean functions f and g, approximate degree of f ◦ g is Ω(approximate degree of f times approximate degree of g).This is the lower bound stated as Result 1.Source: §1 · p. 3

2 Preliminaries

The preliminaries establish notation, define the approximate-degree and composition concepts used in the paper, and collect lemmas supporting the later proof.

2.1 Notations

  • The notation identifies Boolean strings by Hamming weight, defines vector and operator conventions, and introduces a rotation matrix and its tensor power.Functions on the Boolean cube are identified with vectors; matrix norms use the operator norm induced by the Euclidean norm.Source: §2.1 · p. 3

2.2 Definitions

  • Approximate degree is the minimum degree of a polynomial approximating a Boolean function; block composition applies the inner function to disjoint blocks before the outer function.The text also defines bounded approximate degree, which additionally requires the approximant to stay between zero and one on the Boolean cube.Source: §2.2 · pp. 3–4
  • The definitions also cover threshold, promise-threshold, and symmetric functions, as well as trigonometric polynomials and their total frequency.A symmetric function has the same value on inputs of equal Hamming weight.Source: §2.2 · pp. 4–5
  • Squarefree extraction keeps a monomial only when every variable has exponent zero or one, unlike Boolean multilinearization, which replaces positive exponents by one.The text also defines Taylor expansions and their squarefree extraction for analytic functions.Source: §2.2 · pp. 4–5

2.3 Basic Lemmas

  • Basic lemmas provide bounded error-reduced approximants and bounds for squarefree extraction and homogeneous Taylor coefficients of bounded trigonometric polynomials.The error-reduction lemma bounds the new degree by a constant depending on the target error times the original approximate degree.Source: §2.3 · p. 5
  • A dual witness characterizes approximate-degree lower bounds, while a family of block-sampling distributions links polynomial expectations to analytic functions and degree constraints.The sampling lemma defines an expectation over independently sampled blocks and gives a relation for the resulting function when it is analytic near zero.Source: §2.3 · p. 6

3 Overview of Proof Techniques

The proof averages an approximant to the composition over carefully chosen input blocks to recover an approximation to the outer function. For arbitrary inner functions, a dual-witness construction controls both the averaging family’s derivative scale and frequency, yielding the composition lower bound.

3 Overview of Proof Techniques

  • Averaging an approximant Q for f ◦ g over independently sampled blocks can approximate f, but a parameterized sampling family is needed to control the resulting function’s degree or frequency.When each block’s output is prescribed, averaging recovers f; the parameterized families make those approximations part of one controlled function.Source: §3 · p. 6
  • For OR, Bernoulli block sampling gives a bounded polynomial R that approximates f on a scaled Boolean cube, and a dilation bound yields the lower bound on deg Q.Setting p = ay makes each block’s OR output match the corresponding bit with high probability.Source: §3 · p. 6
  • If the composition approximant has degree too small, truncation and squarefree extraction produce an approximant to f of degree below its approximate degree, a contradiction.The argument first bounds the contribution of high-degree terms, then substitutes z = 2y − 1.Source: §3 · p. 7
  • For arbitrary g, a dual witness supplies nested degree subspaces and an operator whose zero-to-one coupling has norm Θ(g deg(g)).The coupling’s singular vectors determine a unit vector used to construct the probability family.Source: §3 · p. 7
  • The resulting unitary-based family has derivative scale κ = Θ(g deg(g)) while preserving a frequency bound, enabling squarefree extraction and truncation to prove the general lower bound.The family’s coordinates form a probability distribution, and its degree-subspace structure controls frequency.Source: §3 · p. 7

4 Warm up: Lower Bounds for Special Classes of Inner Functions

The warm-up proves lower bounds first for arbitrary functions composed with OR, then for promise threshold inner functions. The two cases use bounded averaging and a dilation argument or a trigonometric-polynomial construction with squarefree extraction.

4.1 Arbitrary Function composed with OR Function

  • The OR dilation lemma converts approximation on the scaled cube into a degree lower bound for Q.The lemma assumes R is bounded on [0,1]^n and approximates f on a scaled Boolean cube.Source: §4.1 · pp. 8–9
  • Theorem 9 gives a lower bound for arbitrary f composed with OR_m, equivalently g deg(f ◦ OR_m) ≥ ˜Ω(g deg(f) g deg(OR_m)).The proof averages a bounded approximant over Bernoulli-sampled blocks and applies a dilation bound.Source: §4.1 · p. 8
  • Choosing p = ay makes the blockwise OR outputs match y with high probability, so R(p) approximates f(y) while remaining bounded on the cube.The averaging polynomial has degree at most the degree of Q.Source: §4.1 · pp. 8–9

4.2 Arbitrary Function composed with Promise Threshold Function

  • For promise threshold functions, adjacent Hamming layers provide output-conditioned distributions, and the construction uses κ = (k + 1)(m − k).The distributions are uniform on inputs of weights k and k + 1.Source: §4.2 · p. 9
  • Averaging Q over the constructed families yields a bounded trigonometric polynomial whose squarefree extraction recovers an approximation to f.The averaged function has total frequency at most the degree bound for Q.Source: §4.2 · p. 10
  • If KD ≤ dfκ, the truncation argument produces an approximant to f of degree below df, contradicting the definition of df.The resulting polynomial approximates f within error 1/3.Source: §4.2 · p. 11

5 Lower Bounds for Arbitrary Total Boolean Functions

The section proves a matching approximate-degree composition lower bound for arbitrary total Boolean functions. Its proof builds output-conditioned distributions for the inner function and uses a trigonometric-polynomial construction to transfer the composed approximation to the outer function.

5 Lower Bounds for Arbitrary Total Boolean Functions

  • For arbitrary total Boolean functions f and g, the composition lower bound is g̃deg(f∘g) = Ω(g̃deg(f)g̃deg(g)).The proof assumes nonconstant functions; constant cases follow immediately.Source: §5 · p. 12
  • The proof constructs a family of probability measures from the inner function’s dual witness, supported on inputs conditioned on its two output values.Independent blocks drawn from these measures are averaged against a bounded multilinear approximation to f∘g.Source: §5 · pp. 12–13
  • Averaging yields a bounded trigonometric polynomial of total frequency at most KD, whose squarefree extraction recovers output-conditioned expectations.The proof uses this construction to obtain a polynomial approximating f with degree below its approximate degree unless KD > dfκ.Source: §5 · pp. 12–14
  • Since κ = Θ(g̃deg(g)), the resulting inequality gives the claimed product lower bound.Here D is the approximate degree of f∘g and df is the approximate degree of f.Source: §5 · pp. 12, 14

A Proofs of Lemmas from the Preliminaries

These preliminary proofs establish bounds for homogeneous components of bounded trigonometric polynomials and relate squarefree extraction to expectations under random sign-scaled inputs. They also derive an extraction identity for averages over differentiable families of probability measures.

A Proofs of Lemmas from the Preliminaries

  • Squarefree extraction of a homogeneous polynomial is represented as an expectation after independently scaling its variables by random factors.The proof uses this representation to bound the extraction on the cube from a bound on the original polynomial at inputs with coordinates of magnitude at most 2.Source: A Proofs of Lemmas from the… · pp. 16–17
  • Taylor components of a bounded trigonometric polynomial are bounded by restricting to rational directions and extending the resulting estimate by continuity.The proof reduces each direction to a univariate trigonometric polynomial and applies a derivative estimate.Source: A Proofs of Lemmas from the… · pp. 17–18
  • For analytic averages over probability measures, applying coordinatewise linear functionals removes terms with repeated indices and yields the squarefree extraction identity.The proof identifies the resulting expression as the squarefree extraction evaluated at z/κ.Source: A Proofs of Lemmas from the… · pp. 18–19

B Proofs of Lemmas required for the Main Result

The appendix proves the lemmas used to build output-conditioned distributions for an arbitrary inner Boolean function. A matrix derived from its dual witness supplies a parameter for these distributions, and blockwise averaging produces a bounded trigonometric polynomial with a squarefree-extraction identity.

B Proofs of Lemmas required for the Main Result

  • For a non-constant Boolean function g of degree d, the cited construction gives d/3 ≤ λ = ∥P0AP1∥ ≤ d/2, where Pb projects onto inputs with g=b.For every polynomial of degree at most r, EkMpEℓ = 0 whenever |k−ℓ| > r.Source: B Proofs of Lemmas required for the… · p. 19
  • The parameter κ = 2λ supports a family of probability measures and two distributions supported on inputs where the inner function is respectively 0 and 1.The proof obtains λ from the largest singular value of the relevant matrix block and constructs the measures from unit vectors.Source: B Proofs of Lemmas required for the… · p. 21
  • Averaging a bounded multilinear polynomial over independent blocks drawn from these measures gives a bounded trigonometric polynomial of total frequency at most D.Its squarefree extraction at z/κ equals the expectation under the distribution conditioned on each block’s specified output.Source: B Proofs of Lemmas required for the… · p. 22

C.1 Proofs of Lemmas for function composed with OR

The appendix proves the lower bound for a function composed with OR by combining bounded expectation over independent Bernoulli blocks with a derivative estimate for bounded polynomials. The resulting degree constraint rules out an approximation to the outer function below its approximate degree.

C.1 Proofs of Lemmas for function composed with OR

  • If d√a ≤ df, the derivative-based construction would give a polynomial of degree below df approximating f, a contradiction; hence d√a > df.The argument bounds homogeneous components using higher-derivative estimates and then controls the approximation error.Source: §C.1 · p. 23
  • Averaging a bounded multilinear polynomial over independent Bernoulli bits produces a polynomial of degree at most d that remains in [0,1] on [0,1]^n.The proof factors each monomial across blocks and uses linearity of expectation.Source: §C.1 · p. 24

C.2 Proof of Lemmas for Lower Bound for function composed with promise threshold

The lemmas construct a family of probability measures from adjacent Hamming-weight layers and establish frequency bounds for expectations under these measures. They also show that averaging a bounded block polynomial over independent samples yields a bounded trigonometric polynomial with controlled total frequency.

C.2 Proof of Lemmas for Lower Bound for function composed with promise threshold

  • The measures ρθ are probability measures built using vectors associated with the uniform layers of Hamming weights k and k + 1.The proof checks nonnegativity and normalization.Source: §4.2 · p. 9, §C.2 · p. 24
  • For a set S of size r, the expectation of the monomial XS under ρθ is a trigonometric polynomial with frequency at most r.Source: §C.2 · p. 26
  • For a degree-at-most-D polynomial Q bounded between 0 and 1, independent block sampling yields R bounded between 0 and 1 with total frequency at most D.Each block is sampled from its corresponding ρθ.Source: §C.2 · pp. 26–27
Loading 2609.30139v1…