We describe a new pseudorandom generator for AC0. Our generator -fools circuits of depth d and size M and uses a seed of length O(logd+4M) . The previous best construction for d3 was due to Nisan, and had seed length O(log2d+6M) .A seed length of O(log2d+(1)M) is best possible given Nisan-type generators and the current state of circuit lower bounds; Seed length (logdM) is a barrier for any pseudorandom generator construction given the current state of circuit lower bounds. For d=2, a pseudorandom generator of seed length O(log2M) was known.
展开▼
