Advanced aspects of computational complexity

Computational complexity 1000-218bZO

Complexity theory classifies problems according to their difficulty and explains why some problems are too hard to be solved by good algorithms. This lecture is a continuation of the “Computational complexity” course. We will discuss classic topics of complexity theory that did not fit into that course.

1) Polynomial hierarchy. SAT cannot be solved in linear time and sublinear space.

2) Karp-Lipton and Meter theorems – polynomial hierarchy vs non-uniform circuits.

3) BPP vs polynomial hierarchy.

4) Polynomial hierarchy vs counting problems. Toda’s theorem.

5) Interactive proofs – an alternative definition of polynomial space.

6) Computational security, one-way functions, and pseudorandom generators.

7) Quantum computation (the basics).

8) PCP theorem and hardness of approximation.

9) Proof complexity.

10) Expander graphs and their application to pseudorandom generators.

11) Natural proofs.

12) Computational complexity vs logic. Fagin’s and Immerman-Vardi theorems.

• Ch. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002.

• S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press 2009 (available on-line)

Oral exam. In addition, increasing of the final mark is possible due to solving star problems. Each problem is worth 1 divided by the number of students who correctly solved it.

For PhD students: obligatory participation in solving of star problems, or reading recent literature.