Computational complexity 2017/2018
As ordered by the direction of the institute, the course will be teached in English.
Slides from lectures
- 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)
- 10.10.2017: Kolmogorov complexity, communication compexity, Sipser's theorem, constructible functions, universal machines
- 17.10.2017: hierarchy theorems, gap theorems, boolean circuits (basic definitions)
- 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
- 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
- 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
- 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)
- 21.11.2017: Berman's theorem (proof), relativization & the Baker-Gill-Solovay theorem, decision problems vs search problems, polynomial hierarchy, alternating machines
- 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
- 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
- 12.12.2017 - mid-term exam
- 19.12.2017: derandomization (pseudorandom generators & Yao's theorem); fixed-parameter tractability, treewidth, example: k-colorability, Courcelle's theorem; approximation (example: vertex cover)
- 9.01.2018: interactive proofs
- 16.01.2018: PCP
- 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
Homeworks (series 1, 2, & 3): see here
Other Materials
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.