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

#### Syllabus

• Depth-3 circuits, Valiant's depth reduction
• Traces of finite sets, VC dimension and its relaxations, Sauer-Shelah lemma, Zykov's theorem and hypergraph extensions
• Kraft's inequality, satisfiability coding lemma, depth-3 lower bound for parity
• Arithmetic circuits, bounds from linear algebra and partial derivatives
• Number of zeros and sign patterns of a polynomial map (Bezout's theorem and Warren's theorem)
• Extractors, dispersers, and Ramsey graphs

#### Lectures

• Oct 14 ( Žitná) : N.T. Introduction to circuit lower bounds, Valiant's depth reduction.
• Oct 26: N.T. Satisfiability coding lemma, depth-3 lower bound for parity, PPZ k-SAT algorithm
• Nov 2: N.T. Bottom fan-in 2, projections, Sauer-Shelah lemma, degree-2 polynomials
• Nov 9: N.T. Dimensionality proof of Sauer-Shelah, Sparsification lemma, arbitrary bottom fan-in lower bound for random degree-2 polynomials
• Nov 16: N. T. Frankl's squashing, a variant of VC-dimension, Zykov's theorem
• Nov 23: N. T. Proof of the Sparsification Lemma
• Nov 30: P. H. Introduction to arithmetic circuits, Baur-Strassen lower bound via Bezout's theorem and partial derivatives.
• Dec 7: P. H. Elementary proof of Baur-Strassen theorem by Smolensky, non-constructive lower bounds using Warren's theorem.
• Dec 14: P. H. Khovansky's theorem, lower bounds on the number of addition gates. Lower bounds on symmetric polynomials via dimension of partial derivatives.
• Dec 17: P.P. Introduction to extractors, orthogonal matrices and inner product.
• Jan 4: P.P. Application of the sum-product theorem

#### 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 talebanfard@math.cas.cz