The ability (or inability) to represent or approximate Boolean functions by polynomials is a central concept in complexity theory, underlying interactive and probabilistically checkable proof systems, circuit lower bounds, quantum complexity theory, and more. In this book, the authors survey what is known about a particularly natural notion of approximation by polynomials, capturing pointwise approximation over the real numbers. This book covers recent progress on proving approximate degree lower and upper bounds and describes some applications of the new bounds to oracle separations, quantum query and communication complexity, and circuit complexity. The authors explain how several of these advances have been unlocked by a particularly simple and elegant technique, called dual block composition, for constructing solutions to this dual linear program. They also provide concise coverage of even more recent lower bound techniques based on a new complexity measure called spectral sensitivity. Finally, they show how explicit constructions of approximating polynomials have been inspired by quantum query algorithms. This book provides a comprehensive review of the foundational and recent developments of an important topic in both classical and quantum computing. The reader has a considerable body of knowledge condensed in an accessible form to quickly understand the principles and further their own research.
Author(s): Mark Bun, Justin Thaler
Series: Foundations and Trends in Theoretical Computer Science
Publisher: Now Publishers
Year: 2023
Language: English
Pages: 202
City: Boston
Introduction
Preliminaries
Terminology and Notation
The Cast of Characters
General Upper Bound Techniques
Interpolation
Chebyshev Approximations
Rational Approximation and Threshold Degree Upper Bounds
Error Reduction for Approximating Polynomials
Robust Composition
Polynomials from Query Algorithms
A (Very) Brief Introduction to Query Complexity
Upper Bounds from Quantum Algorithms
Consequences of the Vanishing-Error Upper Bound for OR
More Algorithmically Inspired Polynomials
Algorithmically-Inspired Upper Bound for Composed Functions
Lower Bounds by Symmetrization
Symmetrization Lower Bound for OR
Arbitrary Symmetric Functions
Threshold Degree Lower Bound for the Minsky-Papert CNF
The Method of Dual Polynomials
A Dual Polynomial for ORn
Dual Lower Bounds for Block-Composed Functions
The Approximate Degree of ANDm ORb is (m b)
Hardness Amplification via Dual Block Composition
Some Unexpected Applications of Dual Block Composition
Beyond Block-Composed Functions
Surjectivity: A Case Study
Other Functions and Applications to Quantum Query Complexity
Approximate Degree of AC0
Proof of lem:ambainis
Collision and PTP Lower Bound
Element Distinctness Lower Bound
Spectral Sensitivity
Approximate Rank Lower Bounds from Approximate Degree
A Query Complexity Zoo
Communication Complexity
Lifting Theorems: Communication Lower Bounds from Query Lower Bounds
Communication Lower Bounds via Approximate Rank
Sign-Rank Lower Bounds
Extensions to Multiparty Communication Complexity
Assorted Applications
Secret Sharing Schemes
Learning Algorithms
Circuit Lower Bounds from Approximate Degree Upper Bounds
Parity is not in LTFAC0
Acknowledgements
References
