Algorithms and Lower Bounds: Basic Connections

Lecture 1: Circuit Analysis Algorithms 
Lecture 2: Circuit Complexity and Connections I
Lecture 3: Circuit Complexity and Connections II
Lecture 4: Proof of NEXP Not in ACC
 

This series of talks was part of the Fine-Grained Complexity and Algorithm Design Boot Camp. Videos for each talk area available through the links above.

Speaker: Ryan Williams, Stanford University

This boot camp tutorial will promote a general philosophy shared by the speaker and others: that studying algorithm design and complexity theory "as a single unit" can lead to significant insights that would not be found by studying them in isolation. In this tutorial, the focus will be on Boolean circuits, surveying many known algorithmic results in circuit analysis and lower bound results in circuit complexity, along with intriguing logical connections that have been developed between the two areas. As an example of the methodology in action, we will cover a proof of the result that non-deterministic exponential time does not have ACC0 circuits of polynomial size, via an algorithm for solving the satisfiability problem on ACC0 circuits.