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

Other Materials

Grading Rules