DIMACS Theory of Computing Seminar

Title: On Polynomial Approximations to AC0

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

Date: Wednesday, September 14, 2016 11:00am-12:00pm

Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ


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

See: http://www.math.rutgers.edu/~sk1233/theory-seminar/F16/