Approximate Degree and Quantum Query Lower Bounds via Dual Polynomials
summary
Develops concrete lower bounds for approximate degree and quantum query complexity using linear-program duality and symmetrization, proving block composition yields degree ~sqrt(deg F · deg G) but also constructing a dual polynomials witness to show an AND-of-OR tree has degree Theta(sqrt r · sqrt n). Gives a hardness-amplification that produces an AC0 function with approximate degree n^{3/4} and shows recursion yields n^{1−δ} for constant δ, plus techniques to confine dual support to low Hamming weight.
AI-written summary · about
chapters (15)
- 0:00Intro
- 2:54A Tour of Approximate Degree Lower Bounds
- 9:05The Method of Dual Polynomials
- 11:39Approximate Degree of AND, ORN
- 13:48Approximate Degree of AC
- 15:08Applications of AC° Lower Bound
- 17:00Lower Bound Roadmap
- 17:39Hardness Amplification in AC
- 19:01Our Work: A New Hardness Amplification Theorem for Degree
- 20:32Breaking the Block Composition Barrier
- 21:39Getting to know Surjectivity
- 26:40Details of Stage 2
- 27:23Fixing the AND-OR Dual Polynomial
- 30:28Recap of SURJECTIVITY Lower Bound
- 30:39Open Problems