Abstract
The first session of this talk will take place on Tuesday, September 1 from 1:30 pm – 2:30 pm; the second session of this talk will take place on Wednesday, September 2 from 1:30 pm – 2:30 pm; the fourth session of this talk will take place on Friday, September 4 from 9:30 am – 10:30 am.
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.