Computer Science/Discrete Mathematics Seminar II

Many of the central problems in computational complexity revolve around proving lower bounds on the amount of resources used in various computational models. In this series of talks, we will discuss three standard objects in computational complexity --- propositional proofs, boolean circuits, and communication protocols --- and further describe a three-way connection between them. Much recent work has profitably exploited this connection (in the context of so-called ""lifting theorems"") to translate lower bounds from one model to the other; we will explore several examples of such theorems and suggest some future directions.