Myth creation: Polylogarithmic independence fools AC
Thoughts 2023-08-30
Summary:
Note: See first post of the series myth creation for context. In 1991 [Nis91] constructed a pseudorandom generator for AC (a.k.a. alternating circuits or AC0 circuits), vastly improving the parameters of the pioneering work [AW89]. This is one of my favorite papers ever. (Mini myth creation episode: A large fraction of papers cite [NW94] for this […]