Skip to content Skip to navigation
9/14/2016 11:00 am
CoRE 301

On Polynomial Approximations to AC0

Prahladh Harsha, TIFR (and long-term visitor at Rutgers/DIMACS)

Organizer(s): Pranjal Awasthi and Swastik Kopparty


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.
  Joint work with Srikanth Srinivasan