Selected Topics in Computational Complexity: Mathematical Tools


In this course we focus on methods used in some of the most thrilling results in complexity theory. We will review important tools from finite set theory and extremal combinatorics, linear and higher algebra. During the course of the lectures we will pose many relevant open questions.

We start with a few lectures on the power and limits of depth-3 circuits. We will see the depth reduction argument of Valiant, then proceed to some of the best known lower bounds for these circuits. These results use interesting combinatorial tools such as VC dimension and the Sauer-Shelah lemma which we will cover. We will then present the Satisfiability Coding Lemma which gives tight lower bounds for the parity function and also lies at the heart of the state of the art k-SAT algorithms.

We will also see how to apply tools from linear and higher algebra to obtain lower bounds in the arithmetic circuit setting. This includes the partial derivative method, as well as Baur-Strassen theorem. The latter will be proved using Bezout theorem from algebraic geometry, but a direct proof will also be presented.

Finally we will show an example how tools from computational complexity may serve to solve problems in mathematics. We will see that the quest of constructing the best two source extractors resulted in a dramatic progress in solving the problem about explicit construction of Ramsey graphs.





When and where

The class will be held on Tuesdays at 9am in the Malá Strana building, room S11 (or occasionally Žitná on agreement).

Contact info

Queries about the course should be sent to