A General Composition Theorem for Approximate Degree

arXiv:2609.30139 · cs.CC, quant-ph · Submitted 2026-09-24 · Read on arXiv

cs.CC, quant-ph

Submitted: 2026-09-24

Updated: 2026-09-24

Terminology

• Query Complexity — 9× in this paper · explained in 2 episodes
• Annual Symposium on Foundations of Computer Science — 3× in this paper
• Combinatorial Optimization — 3× in this paper · explained in 2 episodes
• Adam — 2× in this paper · explained in 2 episodes
• Verification — 1× in this paper · explained in 2 episodes

Sources

• A composition theorem for decision tree complexity

Related papers

• Parameterized Hardness of Zonotope Containment and Neural Network Verification
• Hardware-Algorithm Co-Optimization of Early-Exit Neural Networks for Multi-Core Edge Accelerators
• Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM
• Strassen's support functionals coincide with the quantum functionals
• Exponential Quantum Advantage in Numbers-on-Forehead Communication
• Rational degree is polynomially related to degree