CATS-Oct-21-2016
Title[edit]
Approximate Degree, Sign-Rank, and the Method of Dual Polynomials
Speaker[edit]
Justin Thaler
Abstract[edit]
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 complexity, circuit complexity, and oracle separations. Despite its importance, our understanding of approximate degree remains 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. I will describe how the method of dual polynomials has recently enabled progress on a variety of open problems, especially in communication complexity and oracle separations.
Joint work with Mark Bun, Adam Bouland, Lijie Chen, Dhiraj Holden, and Prashant Nalini Vasudevan
