Theory of Computation 2022
Содержание
Classes
Lectures: Monday 13:00 - 14:20 in Pokrovkaya and on this zoomlink by Bruno Bauwens and Alexey Talambutsa
Seminars: Monday 14:40 - 16:00 in Pokrovkaya and on *this zoomlink* by Pavel Zakharov
Dates and Deadlines
Homeworks 1, 2, 3: September 26 October 3 (update of 2.7 and 3.7 on 26/09)
Homeworks 4, 5: October 10
Homeworks 6, 7, 8: November 7
Homeworks 9, 10, 11: November 28
Submit homework in google classroom in this link, code: 27kcgjp
You should upload either scanned handwriting or pdf file into the corresponding section.
Grading
Colloquium: 35%
Homework: 35%
Exam: 30%
Some homework assignments contain extra problems. Each solution of an extra problem will give 1 extra point on the final exam. There will be around 6 extra problems.
Course Materials
The main reference is Sipser's book "Introduction to the theory of computation", chapters 3, 4, 7–10.
For students abroad: the first 5 lectures are covered in chapters 3, 4, 7 and 9.1. Other lectures will be recorded. See also recordings of previous year.
If you need some background in math, consider these two sources:
Lecture notes: Discrete Mathematics, L. Lovasz, K. Vesztergombi
Лекции по дискретной математике (черновик учебника, in Russian)
Summary | Problem list | |
---|---|---|
05.09 | Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. | Problem set 1 |
12.09 | Time and space hierarchy theorems. Time and space constructible functions. | Problem set 2 update 26.09 |
19.09 | Because of various problems, the materials of last 2 weeks were repeated. | Problem set 3 update 25.09 |
26.09 | Complexity class NP. Examples. Polynomial reductions. NP-hardness and NP-completeness. | Problem set 4 |
3.10 | Non-deterministic TMs. Another definition of NP. Proving NP-hardness by reduction from an NP-complete problem. Examples of NP-complete problems. | Problem set 5 |
10.10 | Inclusions between P, NP, and PSPACE. Circuit complexity. Examples. All functions are computed by circuits. Existence of functions with exponential circuit complexity. P is in P/poly. | |
17.10 | P is a subset of P/poly, Cook–Levin theorem, NP-completeness of: subsetsum, set-splitting, 3-colorability and exactly 1-in-3 SAT. | |
31.10 | Space complexity. Classes L, NL, PSPACE and NPSPACE. Directed Reachability is in SPACE(log^2 n). Configuration graph. Inclusions between time and space classes. TQBF problem, its PSPACE-completeness. PSPACE = NPSPACE. NSPACE(s(n)) is in SPACE(s(n)^2) for space constructible s. | |
07.11 | PSPACE completeness of generalized geography. 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. | |
14.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. Most of it is also here | |
21.11 | Streaming algorithms: finding the majority element, computation of the number of different elements in logarithmic space. See Chapts 6.1-6.2 in foundations of datascience by Avrim Blum and others. Another nice chapter in Tim Roughgarden's lecture notes | |
28.11 | Finding the frequent items in streams of data: SpaceSaving and Count-Min Sketch. | |
05.12 | Colloquium. | |
12.12 | Approximation algorithms and complexity of clustering Slides. | Sample exam |
For interested students: parameterized complexity. We review topics from chapters 1, 2, 3, 13 in "Parameterized algorithms" by Cygan, Fomin and others, 2016.
19 Sept: Fixed parameter tracktability and examples. Kernels. presentation.
26 Sept: feedback vertex set, linear programming kernel for vertex cover, k-path problem, exercises on chapters 2 and 3.
3 Oct: Lower bounds using the exponential time hypothesis. slides from a nice course
Exam and Colloquium
All students must attend the colloquium. A list with questions will be given 2 weeks in advance, and will be similar as the list of last year.
The exam consists out of 8 exercises that you must solve in 3 hours time. There will be copies of Sipser's book available (as well as Arora and Barak and Mertens and Moore). You may bring your own copy if you have it, as well as handwritten notes.
You can do the colloquium and the exam online if you received permission from the student office.
Office hours
Bruno Bauwens: Mondays 14h30-20h. Fridays 18h-20h. You can warn in advance by emailing to brbauwens -a- gmail.com
Alexey Talambutsa: First contact by email.