Other titles in Foundations and Trendsยฎ in Theoretical Computer Science
Approximate Degree in Classical and Quantum Computing
Foundations and Trendsยฎ in Theoretical Computer Science
Contents
Approximate Degree in Classical and Quantum Computing
Introduction
Preliminaries
2.1 Terminology and Notation
2.2 The Cast of Characters
General Upper Bound Techniques
3.1 Interpolation
3.2 Chebyshev Approximations
3.3 Rational Approximation and Threshold Degree Upper Bounds
3.4 Error Reduction for Approximating Polynomials
3.5 Robust Composition
Polynomials from Query Algorithms
4.1 A (Very) Brief Introduction to Query Complexity
The vanishing-error approximate degree of OR.
4.3 Consequences of the Vanishing-Error Upper Bound for OR
Collision and PTP.
Element Distinctness.
4.5 Algorithmically-Inspired Upper Bound for Composed Functions
Lower Bounds by Symmetrization
5.1 Symmetrization Lower Bound for OR
5.2 Arbitrary Symmetric Functions
5.3 Threshold Degree Lower Bound for the Minsky-Papert CNF
The Method of Dual Polynomials
6.1 A Dual Polynomial for OR,,
Where did this dual come from?
Two additional properties of VโOR-
Dual Lower Bounds for Block-Composed Functions
7.1 The Approximate Degree of ANDm o OR& is Cl(\/m โข &)
7.2 Hardness Amplification via Dual Block Composition
Increasing degree via composition.
Increasing error via composition.
7.3 Some Unexpected Applications of Dual Block Composition
Lower bound on the vanishing-error approximate degree of OR.
Lower bound on the approximate degree of symmetric functions.
Beyond Block-Composed Functions
8.1 Surjectivity: A Case Study
Approximate degree upper bound.
Approximate degree lower bound.
Threshold degree of SURJ.
8.2 Other Functions and Applications to Quantum Query Complexity
8.3 Approximate Degree of AC0
8.4 Proof of Theorem 8.3
Obtaining the full lemma.
8.5 Collision and PTP Lower Bound
8.6 Element Distinctness Lower Bound
Spectral Sensitivity
Approximate Rank Lower Bounds from Approximate Degree
10.1 A Query Complexity Zoo
10.2 Communication Complexity
10.3 Lifting Theorems: Communication Lower Bounds from Query Lower Bounds
10.4 Communication Lower Bounds via Approximate Rank
Step 1: From high approximate degree to high approximate weight.
Step 2: From high approximate weight to high approximate rank.
Communication applications.
Corollary 10.13. BQPCC(DISJโ) > Q(V^).
10.5 Sign-Rank Lower Bounds
Communication applications.
LTF o MAJ circuit lower bounds.
Open problems on threshold degree and sign-rank.
10.6 Extensions to Multiparty Communication Complexity
Assorted Applications
11.1 Secret Sharing Schemes
11.2 Learning Algorithms
11.3 Circuit Lower Bounds from Approximate Degree lipper Bounds
Worst-case lower bounds from threshold degree upper bounds.
Average-case lower bounds from approximate degree upper bounds.
11.4 Parity is not in LTF o AC0
Acknowledgements
References