Computational complexity 2017/2018

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

Homeworks

Other Materials

• Notes of D. Niwiński
• Notes of B. Klin
• A book Arora, Barak "Computational Complexity: A Modern Approach" (draft)
• Problem book (tutorials)
• Materials of M. Pilipczuk for tutorials: 2016/2017, 2015/2016
• Historical homeworks & exams

Grading Rules

• Homeworks are worth 1.5 pt.
• The mid-term is worth 1.5 pt. The mid-term will be held on 12.12.2017 during the lecture, in room 4420.
• Everyone can approach the June exam (there is no lower limit for points from homeworks / mid-term).
• The final exam (first try) is worth 3 pt.
• The first-term grade encompasses the sum of points from the homeworks, the mid-term, and the exam.
• The final exam (second try) is worth 4.5 pt.
• The second-term grade encompasses the sum of points from the homeworks and the exam.
• The exam (both terms) consists of two parts: the theory, and the practice.
• All solutions (homeworks, mid-term, exam) should be written in English.