Approximate degree of composed boolean functions multiplies exactly
A General Composition Theorem for Approximate Degree
Computational Complexity
Summary
A key question in computer science was whether the difficulty of approximating combined Boolean functions multiplies as expected. The authors proved this is true for all total Boolean functions, meaning the approximate degree of a composition equals the product of the individual approximate degrees. This resolves a long-standing question and matches earlier upper bound results. Their work confirms a precise mathematical relationship when combining these functions.
What this means in practice
- •For complexity theorists: Determine hardness of approximating complex Boolean circuits by analyzing component functions multiplicatively.
- •For algorithm designers: Design more precise approximate algorithms by understanding exact behavior of approximate degree under function composition.
A theory result. No direct application yet.
Authors
Samruddhi Pednekar, Supartha Podder
Abstract
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.