# Computational complexity 2018/2019

[up]
As ordered by the direction of the institute, the course will be teached in English.

## Slides from lectures

1. 2.10.2018: Turing machines; time & space complexity; machines - languages - problems; Church-Turing thesis; random access machines; time vs. space
2. 9.10.2018: Kolmogorov complexity; communication compexity; Sipser's theorem; constructible functions
3. 16.10.2018: universal machines; hierarchy theorems
4. 23.10.2018: gap theorems; boolean circuits; machines vs circuits; machines with advice; uniform sequences of circuits
5. 30.10.2018: circuits of small depth (classes AC and NC); parity is not in AC0
6. 6.11.2018: nondeterministic Turing machines; a model with witnesses; classes of complements; NP intersected with coNP; determinization; reachability in a directed graph and the Savitch theorem
7. 13.11.2018: reductions (Turing, Karp, Levin); complete problems for NP, P, polyL, L, NL, PSPACE; Immerman-Szelepcseny theorem (NL=coNL)
8. 20.11.2018: Ladner's theorem (NP-intermediate problems); dichotomy theorem for CSP; Berman's theorem (single-letter alphabet vs NP); relativization & the Baker-Gill-Solovay theorem; decision problems vs search problems
9. 27.11.2018: polynomial hierarchy; alternating machines; alternating machines vs deterministic machines; probabilistic machines; class RP; amplification
10. 4.12.2018: examples of randomized algorithms: primality testing, checking that a polynomial is nonzero, perfect matchings; amplification for RP (a stronger variant); classes PP, BPP, ZPP (Las Vegas algorithms vs Monte Carlo algorithms); non-uniform derandomization (Adleman theorem); derandomization in practice
11. 11.12.2017 - mid-term exam
12. 18.12.2018: derandomization (pseudorandom generators & Yao's theorem); fixed-parameter tractability, treewidth, example: k-colorability, Courcelle's theorem; approximation (examples: vertex cover, traveling salesman)
13. 8.01.2019: approximation (continued), cryptography, one-way functions, pseudorandom generators, zero-knowledge proofs, quantum computations
14. 15.01.2019: interactive proofs
15. 22.01.2019: PCP
See slides from the previous year.

## Homeworks

Homeworks (series 1, 2, 3): see here