Theory of Computation 2023 — различия между версиями
Bauwens (обсуждение | вклад) |
Bauwens (обсуждение | вклад) |
||
| Строка 61: | Строка 61: | ||
|| [https://www.youtube.com/watch?v=rK5_1KPL9Ko 24.10] || Oracle computation definitions. There exists an oracle ''A'' for which P<sup>''A''</sup> = NP<sup>''A''</sup>. There is an oracle B such that P<sup>''B''</sup> is not equal to NP<sup>''B''</sup>. || [https://www.dropbox.com/scl/fi/j8soyxc3glqiwj9ukd8mj/prob_08.pdf?rlkey=w9n8h8b3sj7uujb51d8vpos4q&dl=0 problem list 8] | || [https://www.youtube.com/watch?v=rK5_1KPL9Ko 24.10] || Oracle computation definitions. There exists an oracle ''A'' for which P<sup>''A''</sup> = NP<sup>''A''</sup>. There is an oracle B such that P<sup>''B''</sup> is not equal to NP<sup>''B''</sup>. || [https://www.dropbox.com/scl/fi/j8soyxc3glqiwj9ukd8mj/prob_08.pdf?rlkey=w9n8h8b3sj7uujb51d8vpos4q&dl=0 problem list 8] | ||
|- | |- | ||
| − | || 07.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 [https://www.youtube.com/watch?v=YSMgVbOqB-8&list=PLm3J0oaFux3YL5vLXpzOyJiLtqLp6dCW2&index=23 here]|| | + | || 07.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 [https://www.youtube.com/watch?v=YSMgVbOqB-8&list=PLm3J0oaFux3YL5vLXpzOyJiLtqLp6dCW2&index=23 here]|| [https://www.dropbox.com/scl/fi/n0eeakvrw2pzirctmlpq7/prob_09.pdf?rlkey=raap4pfnpwouw52qtmbytacdj&dl=0 problem list 9] |
|- | |- | ||
|| 14.11 || Streaming algorithms: finding the majority element, computation of the number of different elements <!-- ''F''<sub>2</sub>--> in logarithmic space. See Chapts 6.1-6.2 in [https://home.ttic.edu/~avrim/book.pdf foundations of datascience] by Avrim Blum and others. Another nice chapter in [http://theory.stanford.edu/~tim/w15/l/l1.pdf Tim Roughgarden's lecture notes] || | || 14.11 || Streaming algorithms: finding the majority element, computation of the number of different elements <!-- ''F''<sub>2</sub>--> in logarithmic space. See Chapts 6.1-6.2 in [https://home.ttic.edu/~avrim/book.pdf foundations of datascience] by Avrim Blum and others. Another nice chapter in [http://theory.stanford.edu/~tim/w15/l/l1.pdf Tim Roughgarden's lecture notes] || | ||
Версия 17:57, 7 ноября 2023
Содержание
Classes
Lectures: Tuesday 18:10 - 19:30 in Pokrovkaya N509 and in zoom by Bruno Bauwens
Seminars: Tuesday 19:40 - 21:00 in Pokrovkaya N509 and on google.meet by Nikita Lukianenko
Telegram group for announcements and discussions invite link. The course is similar to last year's one
Homeworks and dates
Deadlines: every 2 weeks, before the lecture at 17h30. Submit in pdf or fotos of handwritten text in google classrooms, code l4uhnyi. Results. For questions about grading, contact Yaroslav Ivanashev.
Tasks are in the seminar sheets. Problem lists 1 and 2 on 19.09, lists 3 and 4 on 03.10, lists 5 and 6 on 17.10, lists 7 and 8 on 07.11, lists 9 and 10 on 21.11, lists 11 and 12 on 05.12.
Colloquium: 12.12 at the time of the lecture. Rules and questions from last year
Exam: Between 21.12 and 30.12. You may use Sipser's book and the books below.
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)
| Rec | 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 list 1update 05.09 |
| 12.09 | Time and space hierarchy theorems. Time and space constructible functions. | problem list 2 |
| 19.09 | Complexity class NP. Examples. Non-deterministic machines and another definition of NP. Polynomial reductions. NP-hardness and NP-completeness. | problem list 3 |
| 26.09 | NP-completenes of independent set, vertex cover, dominating set, NAE-3SAT, 3colorability. | problem list 4update 27.09 |
| 03.10 | Circuit complexity. Classes AC^i, NC^i, P/poly. All functions are computed by circuits. Existence of functions with exponential circuit complexity. NC1 = Boolean formulas of polynomial size. P is in P/poly (without proof). Addition in AC0. Multiplication is in NC1. circuit_notes.pdf | problem list 5update 17.10 |
| 10.10 | Proof that P is in P/poly. Proof of Cook Levin theorem. NP-completeness of: exact 1-in-3SAT, subsetsum, Hamiltonian path. Strong NP-completeness. coNP and coNP-completeness. | problem list 6 |
| 17.10 | Directed Reachability is in SPACE(log^2 n). TQBF problem, its PSPACE-completeness. PSPACE = NPSPACE. NSPACE(s(n)) is in SPACE(s(n)^2) for space constructible s. | problem list 7update 25.10 |
| 24.10 | 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. | problem list 8 |
| 07.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 | problem list 9 |
| 14.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 | |
| 21.11 | More streaming algorithms: calculation F_0 moments, Hash functions, finding the frequent items in streams of data: SpaceSaving. Lower bounds using communication complexity. | |
| 28.11 | Parameterized complexity the classes FPT and XP. Kernelization. Examples for vertex cover and k-paths problem. Lower bounds using exponential time hypothesis. presentation. | |
| 05.12 | FPT algorithms for feedback vertex set and k-path problem, linear programming kernel for vertex cover, graph algorithms with bounded treewidth. | |
| 12.12 | Colloquium | |
| 12.19 | Approximation algorithms and complexity of clustering. Approximation hardness. Slides. | Sample exam |
Project (for PI students)
During the 3rd module Januari till March 2023 there are projects where you need to implement algorithms from parameterized complexity. (For example, for the vertex cover algorithm and disjoint paths problems.) A grader will check whether your algorithm reaches certain time limits.
Additional reading
Both books below contain a lot of extra materials and describe more recent discoveries in computational complexity. The first book has a gentle and pleasant style. The second book is a rigorous textbook for students theoretical computer science at the beginning master level.
C. Moore and S. Mertens, The nature of computation, 2011.
S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009.
This is an advanced textbook with background on parameterized algorithms.
M. Cygan, F. Fomin and 6 others, Parameterized algorithms, 2016
Grading
For AMI students:
Final score = 0.35 * [score homework] + 0.35 * [score colloquium] + 0.3 * [score exam]
For PI students (the course is called "computational complexity" and takes 3 modules):
Final score = 0.25 * [score homework] + 0.25 * [score colloquium] + 0.25 * [score exam] + 0.25 * [score project]
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.
Rounding. Only final grades are rounded. Arithmetic rounding is used.
Autogrades. If only 6/10 for the exam is needed to get a final score of 10/10, then this will be given automatically.
Office hours
Bruno Bauwens: Wednesdays 13h00-16h30. Fridays 14h-20h. Better send me an email in advance.
Nikita Lukianenko:
