About the Courses

Boolean Circuit Complexity
(Benjamin Rossman)

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 (AC⁰ and AC⁰[Mod_p]), 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 AC⁰ 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
(Ryan Williams)

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:

1. given a circuit, determine a nontrivial property of the function it computes,
2. given the truth table of a Boolean function, determine a nontrivial property of circuits computing it,
3. 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.

Prerequisites

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 Barak.

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).