Justin Thaler: Approximate Degree and the Method of Dual Polynomials

The eps-approximate degree of a Boolean function is the minimum degree of a real polynomial that point-wise approximates f to error eps. Approximate degree has wide-ranging applications in theoretical computer science, from computational learning theory to communication, query, and circuit complexity. Despite its importance, our understanding of approximate degree remains somewhat limited, with few general results known.

The focus of this talk will be on a relatively new method for proving lower bounds on approximate degree: specifying emph{dual polynomials}, which are dual solutions to a certain linear program capturing the approximate degree of any function. After surveying earlier work on approximate degree, I will describe how the method of dual polynomials has recently enabled progress on several open problems.

Joint work with Mark Bun.