Approximate Degree in Classical and Quantum Computing

摘要

The approximate degree of a Boolean function f captures how well f can be approximated pointwise by low-degree polynomials. This monograph surveys what is known about approximate degree and illustrates its applications in theoretical computer science.A particular focus of the survey is a method of proving lower bounds via objects called dual polynomials. These represent a reformulation of approximate degree using linear programming duality. We discuss in detail a recent, powerful technique for constructing dual polynomials, called "dual block composition".