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 talk we will continue our survey of the connections between three central models (proofs, communication, circuits) from last week, sketching several examples of the so-called "lifting theorems" for proving lower bounds.