A General Composition Theorem for Approximate Degree
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→{0,1} and g:{0,1}m→{0,1}, deg̃(f∘ g) = Θ ( deg̃(f) deg̃(g) ), 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.
Related
- Approximate synthesis of general single-qubit unitaries over the Clifford+√T gate set
- A general no-go theorem for loss-free optical torque, and its enantiomer-differential escape route
- Gravitational Memory: an approximate description
- High-Rank Encoding Can Improve Approximate Quantum Error Correction
- Approximate Synthetic Spectra of Quantum Systems Associated with Compact Lie Groups
BibTeX
@misc{pednekar2026general,
title = {{A General Composition Theorem for Approximate Degree}},
author = {Samruddhi Pednekar and Supartha Podder},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.30139},
eprint = {2609.30139},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30139},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A General Composition Theorem for Approximate Degree
AU - Samruddhi Pednekar
AU - Supartha Podder
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2609.30139
UR - https://arxiv.org/abs/2609.30139
AB - 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}, deg̃(f∘ g) = Θ ( deg̃(f) deg̃(g) ), 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.
ER -