Title: Pseudorandom generators for read-once ACC^0_m
Speaker: Srikanth Srinivasan, DIMACS
Date: Wednesday, November 9, 2011 11:00-12:00pm
Location: CoRE Bldg, CoRE 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
ACC^0_m is the family of constant depth polynomial-size circuits with AND, OR, NOT and MOD_m gates, where m is a fixed constant and MOD_m gates return 1 if their input has hamming weight divisible by m. In the absence of MOD_m gates, a seminal result due to Nisan (Combinatorica 1991) gives explicit pseudorandom generators (PRGs) for such circuits of polylogarithmic seedlength. We have no PRG of comparable efficiency in the presence of MOD_m gates for any m.
We make progress on this problem by constructing explicit PRGs for ACC^0_m under the read-once condition: that is, for functions that are computed by ACC^0_m formulas where each input bit is read at most once. Our PRGs have polylogarithmic seedlength, which improves exponentially on earlier results of Viola (SICOMP 2007) and Bogdanov et al. (FOCS 2011), though these other results also work for more general models.
Our PRG and its analysis are combinatorial, relying on an understanding of what happens to the bias of a read-once formula under random restrictions.
Joint work with Dmitry Gavinsky (NEC) and Shachar Lovett (IAS).