Prahladh Harsha: On polynomial approximations to AC0

Abstract
In this talk, we will discuss some questions related to polynomial approximations of AC0. A classic result due to Tarui (1991) and Beigel, Reingold, and Spielman (1991), states that any AC0 circuit of size s and depth d has an ε-error probabilistic polynomial over the reals of degree at most \((log(s/ε))^{O(d)}\). We will have a re-look at this construction and show how to improve the bound to \((log s)^{O(d)}⋅log(1/ε)\), which is much better for small values of ε.

 As an application of this result, we show that \((log s)^{O(d)}⋅log(1/ε)\)-wise independence fools AC0, improving on Tal's strengthening of Braverman's theorem that \((log(s/ε))^{O(d)}\)-wise independence fools AC0. Time permitting, we will also discuss some lower bounds on the best polynomial approximations to AC0.