Fighting Boolean Circuits: New Correlation Bounds and Pseudorandom Generators

The general problem of proving limitations on what efficient algorithms can accomplish has been the subject of much research over the past four decades. In this talk, we consider the specific question of bounding the power of Boolean circuits. We discuss three generic questions: those of proving lower bounds, correlation bounds, and constructing Pseudorandom generators (PRGs) for different classes of Boolean circuits. We look at the major results in these directions and the important questions that need to be tackled next.

In the process, we motivate the question of proving correlation bounds and constructing PRGs for bounded-depth circuits. We then describe our own results: correlation bounds for AC^0 with a few symmetric gates, and explicit PRGs against read-once ACC^0 (this is joint work with Shachar Lovett (IAS, Princeton) and Dmitry Gavinsky (NEC Research Labs, Princeton)).