CS 789 THEORY SEMINAR [home]

Speaker:     Dexter Kozen, Cornell University
Date:          August 29 (and maybe September 5), 2005
Title:          Circuit Lower Bounds and Relativized PH = PSPACE

Abstract:

Lower bounds for Boolean circuits of constant depth are interesting not only from the point of view of circuit complexity, but also for their consequences regarding the structure of the relativized polynomial-time hierarchy.

The first lower bound results for constant-depth circuits were obtained by Furst, Saxe and Sipser (FSS) and Ajtai in the mid 1980's. They showed that the parity function, among others, cannot be computed in AC0 (constant depth and polynomial size). FSS also observed that sufficiently strong superpolynomial lower bounds on the size of constant-depth circuits for parity imply the existence of an oracle separating PH from PSPACE, but unfortunately their results were not strong enough to achieve this. A series of later papers improved the bounds, culminating in a nearly optimal result of Haastad in 1986. Haastad's main argument is encapsulated in a powerful lemma known as the switching lemma, which has since found many other applications. This result provides the necessary lower bounds to construct the desired oracle separating PH from PSPACE.

The original FSS paper was one of the first to use the probabilistic method in existence proofs. In this method, one proves the existence of an artifact by showing that it appears with nonzero probability at the end of some random process.

In this lecture (and the next if I run over, which I probably will), I will introduce this area and give new proofs of the FSS/Ajtai result that parity is not in AC0 and the Haastad switching lemma.