We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Approximate Degree: A Survey

Formal Metadata

Title
Approximate Degree: A Survey
Title of Series
Number of Parts
17
Author
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
The epsilon-approximate degree of a Boolean function is the minimum degree of a real polynomial that pointwise approximates f to error epsilon. Approximate degree has wide-ranging applications in theoretical computer science, from computational learning theory to communication complexity, circuit complexity, oracle separations, and even cryptography. This talk will survey what is known about approximate degree and its many applications, including striking recent progress on proving approximate degree lower bounds. This survey will also function as a primer for Mark Bun's followup talk.