Tata Institute of Fundamental Research
On Polynomial Approximations to AC0
STCS Seminar
Speaker:
Prahladh Harsha
Organiser:
Rahul Vaze
Date:
Tuesday, 30 Aug 2016, 16:30 to 17:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
In this talk, we will survey questions related to polynomial approximations of AC0. A classic result due to Tarui (1991) and Beigel, Reingold, and Spielman (1991), that any AC0 circuit of size s and depth d has an ε-error probabilistic polynomial over the reals of degree (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).
| Speaker: | Prahladh Harsha |
| Organiser: | Rahul Vaze |
| Date: | Tuesday, 30 Aug 2016, 16:30 to 17:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
In this talk, we will survey questions related to polynomial approximations of AC0. A classic result due to Tarui (1991) and Beigel, Reingold, and Spielman (1991), that any AC0 circuit of size s and depth d has an ε-error probabilistic polynomial over the reals of degree (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).
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).