Dept Banner
Dept Banner


Download as iCal file

DIMACS Theory of Computing Seminar

On polynomial approximations to AC0

Location:  CoRE 301
Date & time: Wednesday, 14 September 2016 at 11:00AM -

Prahladh Harsha, TIFR (long term visitor at RU/DIMACS)


"On polynomial approximations to AC0"

Time: 11:00 AM
Location: CoRE 301
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.

Joint work with Srikanth Srinivasan

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.

Contact Us

HillCenter small

Department of Mathematics

Department of Mathematics
Rutgers University
Hill Center - Busch Campus
110 Frelinghuysen Road
Piscataway, NJ 08854-8019, USA

Phone: +1.848.445.2390
Fax: +1.732.445.5530