Videos

Proofs, Circuits, Communication, and Lower Bounds in Complexity Theory

Presenter
February 11, 2020
Abstract
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.