About the Courses
Boolean Circuit Complexity
This course will delve into lower bound for Boolean circuits – a combinatorial approach to P vs. NP (and other questions). We mainly focus on a few restricted classes where significant progress has been achieved, namely: bounded-depth circuits (AC0 and AC0[Modp]), monotone circuits, and formulas. We begin with a review of classic techniques from the 1940’s-80’s: counting, gate elimination, switching lemmas, and the polynomial method. We then describe some recent results that extend and sharpened these techniques. The latter part of the course will zoom in on the average-case complexity of subgraph isomorphism problems, such as Clique and st-Connectivity, on Erdős-Rényi random graphs; we present lower bounds for this important family of problems in both the AC0 and (unbounded-depth) monotone settings.
The material in this course should be accessible to beginning graduate students. Chapters 6 and 12-14 of Arora-Barak are recommended reading for background.
Algorithms and Lower Bounds: A Love Story
At a high level, my plan is to start with a series of lectures on what I call "circuit analysis algorithms" which can take (at least) three forms:
- given a circuit, determine a nontrivial property of the function it computes,
- given the truth table of a Boolean function, determine a nontrivial property of circuits computing it,
- given oracle access to a Boolean function, "learn" a circuit for the function (or an approximation of the function) via oracle queries.
After that, I plan to give a few lectures on intimate connections that have been discovered between such analysis algorithms and circuit lower bounds. In general, from sufficiently "good" circuit analysis algorithms, one can conclude strong circuit complexity lower bounds, and sometimes the converse holds as well.
Finally, I will give a few lectures on concrete lower bounds that have been proved via such connections, such as NEXP not in ACC.
The summer school is intended to be accessible to beginning PhD students
in theoretical computer science, but the courses will assume knowledge of circuit complexity.
Participants not previously familiar with this topic (or needing to
refresh their memories) are expected to prepare by studying material
equivalent to Chapters 6 (Boolean circuits) and 14 (Circuit lower
bounds) in "Computational Complexity: A Modern Approach" by Arora and
It might also be helpful, though it is not required, to be familiar with
the material in Chapters 12 (Decision trees), 13 (Communication
complexity), 20 (Derandomization), and 23 (on why proving circuit lower
bounds is hard).