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.

Instructors

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

Literature

Extremal combinatorics and circuits:
- Frankl P., Tokushige N., Extremal Problems for Finite sets, American Mathematical Society, 2018.
- Paturi R., Pudlák P., Zane F., Satisfiability Coding Lemma, Chicago Journal of Theoretical Computer Science, 1999.
- Paturi R., Saks M., Zane F., Exponential lower bounds for depth-3 Boolean circuits, Computational Complexity, 2000.
- Impagliazzo R., Paturi R., Zane F., Which problems have strongly exponential complexity? , J. Computer System Sciences, 2001.
- Viola E., Power of Small Depth Computation, Foundations and Trends in TCS, 2009.
- Frankl P., Gryaznov S., Talebanfard N., A variant of the VC-dimension with Applications to Depth-3 Circuits, ITCS'22.
Algebra:
- Alon N., Tools from higher algebra, Handbook of Combinatorics, 1995.

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