Speaker: Justin Thaler
Affiliation: Georgetown University
Title: Approximate Degree, Sign-Rank, 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, yet 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 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