[Theory Seminar] Justin Thaler

November 16, 2016 @ 12:00 pm – 1:00 pm

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