Theory of Computation 2021
Classes
Tuesdays 14:40–17:40, ruz
Lectures: 14:40 in room M303, also streamed here parallel session
Seminars: 16:20 in room M203, also streamed here
Dates and Deadlines
Please send your homework by e-mail to both lecturers.
Homework 1, deadline: October 5, 14:00
Homework 2, deadline: November 2, 14:00
Homework 3, deadline: December 7, 14:00
Colloquium: December 7, 14:40–17:40
Grading
Colloquium: 35%
Homework: 35%
Exam: 30%
Course Materials
The main reference is Sipser's book "Introduction to the theory of computation", chapters 3, 7–10.
If you need some background in math, consider these two sources:
Lecture notes: Discrete Mathematics, L. Lovasz, K. Vesztergombi
Лекции по дискретной математике (черновик учебника, in Russian)
Date | Summary | Problem list |
---|---|---|
07.09 | Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples (one, two). Time and space complexity. Complexity classes P, PSPACE, EXP. | Problem set 1 |
14.09 | Time and space hierarchy theorem. Time and space constructible functions. | Problem set 2 |
21.09 | Complexity class NP. Examples. Inclusions between P, NP and PSPACE. Non-deterministic TMs. Another definition of NP. Polynomial reductions, their properties. NP-hardness and NP-completeness, their properties. | |
28.09 | Proving NP-hardness by reduction from an NP-complete problem. Examples of NP-complete problems. | |
05.10 | Circuit complexity. Examples. All functions are computed by circuits. Existence of functions with exponential circuit complexity. P is in P/poly. | |
12.10 | Cook–Levin theorem. | |
26.10 | Space complexity. | |
02.11 | Oracle computation definitions. There exists an oracle A for which PA = NPA. There is an oracle B such that PB is not equal to NPB. | |
09.11 | Probabilistic computation. Probabilistic machines, the class BPP, invariance of the definition BPP for different thresholds, RP, coRP, PP, ZPP. BPP is in P/poly. | |
16.11 | Streaming algorithms: finding the majority element, computation of the moment F2 in logarithmic space. | |
23.11 | Finding the frequent items in streams of data: SpaceSaving and Count-Min Sketch. | |
30.11 | Approximation algorithms. Approximate solutions for Vertex Cover, Weighted Vertex Cover, and TSP. | |
07.12 | Colloquium. | |
14.12 | Complexity of clustering: an exact algorithm for maximising the inter-cluster distance and an approximate algorithm for minimising the intra-class distance. |
For students interested in arameterized complexity.
14 Sept: Efficient algorithms presentation.
21 Sept: Topics from chapter 1 and 2 in "Parameterized algorithms" by Cygan, Fomin and others, 2016.
28 Sept: The W-hierarchy, chapter 13 in the book.
Office hours
Person | Monday | Tuesday | Wednesday | Thursday | Friday |
---|---|---|---|---|---|
Bruno Bauwens, S834, Zoom | 14:00-20:00 | ||||
Sergei Obiedkov, T915, Zoom | 16:30–18:00 | 16:30–18:00 |