BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Approximate Degree: A Survey Thaler, Justin


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.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International