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.