Speaker: Justin Thaler, Harvard University
Title: Approximate Degree and the Method of Dual Polynomials
Abstract:
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 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.
Based on joint work with Mark Bun.