2019 School: Lectures

The school was comprised of four main lecture courses, based on some of the most developed approaches to computational complexity today.

  1. Boolean circuits and lower bounds. (Rahul Santhanam, University of Oxford).
  2. Algebraic circuits and geometric complexity. (Peter Bürgisser, Technical University Berlin).
  3. Proof complexity and bounded arithmetic; (Samuel Buss, University of California San Diego).
  4. Machine-free complexity (descriptive and implicit complexity). (Anuj Dawar, University of Cambridge and Ugo Dal Lago, University of Bologna)

In addition to these broad-ranging themes, there will also be three more focussed topics, providing examples of (already established or potential) interactions between logic, algebra and complexity:

  1. Constraint satisfaction problems. (Libor Barto, Charles University in Prague).
  2. Communication complexity. (Sophie Laplante, Paris 7 University).
  3. Duality in formal languages and logic. (Daniela Petrisan, Paris 7 University).