Computational complexity 2017/2018

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

Slides from lectures

  1. 3.10.2017: Turing machines, time & space complexity, machines - languages - problems, Church-Turing thesis, random access machines, time vs. space, Sipser's theorem (statement only)
  2. 10.10.2017: Kolmogorov complexity, communication compexity, Sipser's theorem, constructible functions, universal machines
  3. 17.10.2017: hierarchy theorems, gap theorems, boolean circuits (basic definitions)
  4. 24.10.2017: machines vs circuits, machines with advice, uniform sequences of circuits, circuits of small depth (classes AC and NC), parity is not in AC0
  5. 31.10.2017: parity is not in AC0 (continued), extensions of AC0, nondeterministic Turing machines, a model with witnesses, classes of complements, NP intersected with coNP, determinization
  6. 7.11.2017: determinization, reachability in a directed graph and the Savitch theorem, reductions (Turing, Karp, Levin), complete problems for NP, P, polyL, L, NL
  7. 14.11.2017: PSPACE-completeness of QBF, Immerman-Szelepcseny theorem (NL=coNL), Ladner's theorem (NP-intermediate problems), dichotomy conjecture for CSP, Berman's theorem (single-letter alphabet vs NP)
  8. 21.11.2017: Berman's theorem (proof), relativization & the Baker-Gill-Solovay theorem, decision problems vs search problems, polynomial hierarchy, alternating machines
  9. 28.11.2017: alternating machines vs deterministic machines, probabilistic machines, class RP, amplification, examples of randomized algorithms: primality testing, checking that a polynomial is nonzero
  10. 5.12.2017: amplification for RP (a stronger variant), example randomized algorithm: perfect matchings, classes PP, BPP, ZPP (Las Vegas algorithms vs Monte Carlo algorithms), non-uniform derandomization (Adleman theorem), derandomization in practice
  11. 12.12.2017 - mid-term exam
  12. 19.12.2017: derandomization (pseudorandom generators & Yao's theorem); fixed-parameter tractability, treewidth, example: k-colorability, Courcelle's theorem; approximation (example: vertex cover)
  13. 9.01.2018: interactive proofs
  14. 16.01.2018: PCP
  15. 23.01.2018: approximation (continued), cryptography, one-way functions, pseudorandom generators, zero-knowledge proofs, quantum computations
The exam (9.02.2018): test / problems / solutions

See slides from the previous year.


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

Other Materials

Grading Rules

Licznik: 1948

Valid HTML 4.0!