Theory of Computation 2022

Classes

Lectures: Monday 13:00 - 14:20 by Bruno Bauwens and Alexey Talambutsa

Seminars: Monday 14:40 - 16:00 by Pavel Zakharov

Dates and Deadlines

Homeworks 1, 2, 3: September 26 October 3 (update of 3.7 on 25/09)

Homeworks 4, 5: October 10

Homeworks 6, 7, 8: November 7

Homeworks 9, 10, 11: November 28

Email: homeworks to brbauwens -a- gmail.com. Start the subject line with COMP-HW

Grading

Colloquium: 35%
Homework: 35%
Exam: 30%

Homework Grading

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.

Here's the classroom link for your homeworks:

• Link, code: 27kcgjp

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)

	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.
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: exercises on chapters 2 and 3, treewidth

3 Oct: The W-hierarchy, chapter 13 in the same book.

Office hours

Bruno Bauwens: Mondays 14h30-20h. Fridays 18h-20h. Also on Tuesdays, but warn ahead: brbauwens -a- gmail.com

Alexey Talambutsa: First contact by email.