Main Lectures

Course 1. Circuit Complexity.

Lecturer: Rahul Santhanam (University of Oxford).

The course will touch upon the following topics: circuit lower bounds, algorithmic method, Minimum Circuit Size Problem, natural proofs and meta-mathematics of lower bounds.

[Blackboard lectures.  No slides available!]

Course 2. Proof Complexity and Bounded Arithmetic.

Lecturer: Samuel Buss (University of California San Diego).

The first talks will cover proof complexity, including Frege, extended Frege, resolution, cutting planes, simulations, Craig interpolation, automatizability, CDCL solvers and DRAT proof systems. The second set of talks will be an introduction to bounded arithmetic, total NP functions, and the Cook and Paris-Wilkie translations to propositional proofs.

The slides are available here.

Course 3. Algebraic and Geometric Complexity.

Lecturer: Peter Bürgisser (Technical University Berlin).

After presenting some surprising algorithms, we discuss classical ideas leading to the only known nonlinear complexity lower bounds in the model of unrestricted arithmetic circuits: those are Strassen's degree bound, combined with a method for automatic differentiation (nowadays gaining prominence as part of the backpropagation algorithm for neural networks).

In the second part of the tutorial, we discuss the crucial role of Valiant's VP vs VNP conjecture. We outline the more recent ideas of viewing this an orbit closure problem and how to attack it using tools of invariant and representations theory.

[Blackboard lectures.  No slides available!]

Course 4. Machine-free Complexity (Descriptive Complexity and Implicit Complexity)

Lecturers: Anuj Dawar (University of Cambridge) and Ugo dal Lago (University of Bologna).

Descriptive Complexity.  This three-hour tutorial will provide an introduction to the subject of descriptive complexity theory. The first 90 minute talk will cover the classical theory of descriptive complexity as it was developed in the 1970s and 1980s. I will give an account of Fagin's theorem characertizing NP, and other results capturing complexity classes on ordered structures. I will also explore the question of a logic for PTIME and look at methods of proving inexpressiblity in logic.

The second 90 minute session will focus on more contemporary themes in descriptive complexity, focussing on the expressive power of FPC, fixed-point logic with counting. I'll explain the importance of this class and establish connections with circuit models and linear programming. I will also explain upper and lower bounds on the power of FPC.

Slides: First Lecture; Second Lecture.

Implicit Complexity.  The aim of implicit computational complexity (ICC in the following) is the one of giving machine-free characterisations of complexity classes based on tools from mathematical logic, and in particular from proof theory and recursion theory. This three-hour tutorial on the subject does not aim to be an exhaustive description of the field, which has developed quite substantially in the last thirty years. Rather, after giving a bird-eye view on the subject, I will focus on some themes which have been among the central ones in ICC lately, namely the characterisation of complexity classes through the Curry-Howard correspondence, the problem of intentional expressivity of ICC systems, and some new challenges ICC is facing nowadays, in particular related to probabilistic and concurrent computation.

Slides.

Focussed Lectures

Course A. Communication Complexity.

Lecturer: Sophie Laplante (Paris 7 University).

Course B. Constraint Satisfaction Problems.

Lecturer: Libor Barto (Charles University).

What kind of mathematical structure in computational problems allows for efficient algorithms? This fundamental question now has a satisfactory answer for a rather broad class of computational problems, so called fixed-language Constraint Satisfaction Problems (CSPs) - it has turned out that their complexity is captured by a certain specific form of symmetry. 

In the first talk, I will give examples of CSPs, explain the connection to symmetries, and briefly discuss some of the major results and research directions. The second talk will focus on recent developments in one of these directions, the promise CSPs, which include problems such as finding a 137-coloring of a 3-colorable graph.

Slides: Part 1; Part 2.

Course C. Duality Theory and Complexity.

Lecturer: Daniela Petrisan (Paris 7 University).