Theory of Computation 2022 — различия между версиями
Bbauwens (обсуждение | вклад) |
Bbauwens (обсуждение | вклад) |
||
| Строка 36: | Строка 36: | ||
| − | The main reference is Sipser's book "Introduction to the theory of computation", chapters 3, 7–10. | + | 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 [http://wiki.cs.hse.ru/Theory_of_Computation_2021 previous year]. | ||
If you need some background in math, consider these two sources:<br> | If you need some background in math, consider these two sources:<br> | ||
Версия 14:41, 3 октября 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 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
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.
