Computational complexity 2018/2019
As ordered by the direction of the institute, the course will be teached in English.
Slides from lectures
See slides from the previous year.
- 2.10.2018: Turing machines; time & space complexity; machines - languages - problems; Church-Turing thesis; random access machines; time vs. space
- 9.10.2018: Kolmogorov complexity; communication compexity; Sipser's theorem; constructible functions
- 16.10.2018: universal machines; hierarchy theorems
- 23.10.2018: gap theorems; boolean circuits; machines vs circuits; machines with advice; uniform sequences of circuits
- 30.10.2018: circuits of small depth (classes AC and NC); parity is not in AC0
- 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
- 13.11.2018: reductions (Turing, Karp, Levin); complete problems for NP, P, polyL, L, NL, PSPACE; Immerman-Szelepcseny theorem (NL=coNL)
- 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
- 27.11.2018: polynomial hierarchy; alternating machines; alternating machines vs deterministic machines; probabilistic machines; class RP; amplification
- 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.12.2017 - mid-term exam
- 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)
- 8.01.2019: approximation (continued), cryptography, one-way functions, pseudorandom generators, zero-knowledge proofs, quantum computations
- 15.01.2019: interactive proofs
- 22.01.2019: PCP
Homeworks (series 1, 2, 3): see here
- 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
- Tutorials (group 3):
- Homeworks are worth 1.5 pt.
- The mid-term is worth 1.5 pt.
The mid-term will be held on 11.12.2018 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.