Theory of Computation 2024 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показано 66 промежуточных версии этого же участника)
Строка 2: Строка 2:
 
= Classes =
 
= Classes =
  
−
Lectures: TBA in Pokrovkaya TBA and in [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom] by [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens]  
+
Lectures: Wednesdays 18h10 in Pokrovkaya room N507 and in [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom] by [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens].
  
−
Seminars: TBA in Pokrovkaya TBA and in TBA by [https://www.hse.ru/en/org/persons/190890122 Yaroslav Ivanashev]
+
Seminars: After the lecture in room N507 and on the same zoomlink by [https://www.hse.ru/en/org/persons/190890122 Yaroslav Ivanashev]
  
 
Telegram group for announcements and discussions [https://t.me/+axdYo-H6h35iNWU0 invite link.] The course is similar to [http://wiki.cs.hse.ru/Theory_of_Computation_2023 last year's one] For PI students the course is called ''computational complexity'' and has a 2nd part in Febr--March 2025.  
 
Telegram group for announcements and discussions [https://t.me/+axdYo-H6h35iNWU0 invite link.] The course is similar to [http://wiki.cs.hse.ru/Theory_of_Computation_2023 last year's one] For PI students the course is called ''computational complexity'' and has a 2nd part in Febr--March 2025.  
 +
 +
[https://docs.google.com/spreadsheets/d/1gk4wvUV5sHYWj1INOMbuUPspCsMpqul_KPB3npp7PzQ/edit?usp=drive_link Results].
 +
 +
= Exam =
 +
 +
Dec 19th 9h30 room R503.
 +
 +
5 or 6 questions with the same difficulty as the homework questions. You have 3 hours time.
 +
 +
Each year, 1 of the questions is to prove that some problem is NP-complete. Do not forget to say why the problem is in NP.
 +
 +
Copies of Sipser's book, Arora&Barak, Mertens&Moore, will be available. (I you have these books or printed parts of them, please bring it.) Also, personal handwritten notes are allowed, but nothing else.  [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam].
  
  
 
= Homeworks =
 
= Homeworks =
  
−
Deadlines: every 2 weeks, before the lecture at 17h30. Submit in pdf or fotos of handwritten text in (link google classrooms TBA), code TBA. Results TBA. Questions [https://t.me/ivanashev Yaroslav Ivanashev].
+
Deadlines: every 2 weeks, before the lecture at 18h00. Submit in pdf or fotos of handwritten text in [https://classroom.google.com/c/NzEzMTc2NTcyNTI1?cjc=5osql6c google classrooms]. [https://docs.google.com/spreadsheets/d/1gk4wvUV5sHYWj1INOMbuUPspCsMpqul_KPB3npp7PzQ/edit?usp=drive_link Results]. Questions: Yaroslav Ivanashev.
  
 
Tasks are in the problem lists from the seminar. Deadlines: problem lists 1 and 2: at the start of 3rd lecture, lists 3 and 4 at the start of the 5th lecture, etc.
 
Tasks are in the problem lists from the seminar. Deadlines: problem lists 1 and 2: at the start of 3rd lecture, lists 3 and 4 at the start of the 5th lecture, etc.
 +
 +
Late policy: 1 homework can be submitted at most 24h late without explanations.
  
  
 
= Course Materials =
 
= Course Materials =
  
−
The main reference is Sipser's book "Introduction to the theory of computation", chapters 3, 4, 7–10.
+
The main reference is Sipser's book "Introduction to the theory of computation", chapters 3, 4, 7–9.
  
 
If you need some background in math, consider:
 
If you need some background in math, consider:
Строка 28: Строка 42:
 
!  Rec !! Summary !! Problem list
 
!  Rec !! Summary !! Problem list
 
|-
 
|-
−
  || [https://www.youtube.com/watch?v=XcApxCiymew 21.09] || Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. || [https://drive.google.com/file/d/19T2NKv8gWpLyYQtittxr9lzISdlIJguN/view?usp=sharing problem list 1]
+
  || [https://www.youtube.com/watch?v=-VIr385nKVk 23.09] || Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. [https://drive.google.com/file/d/15yDi0vZVVAw-2UuBu5Mxc17KWLzSIFML/view?usp=sharing Notes]|| [https://drive.google.com/file/d/19T2NKv8gWpLyYQtittxr9lzISdlIJguN/view?usp=sharing problem list 1]
 
|-
 
|-
 
|-
 
|-
−
|| [https://www.youtube.com/watch?v=tnq5BkcGfk0 ??.09] || Time and space hierarchy theorems. Time and space constructible functions. ||  
+
|| [https://www.youtube.com/watch?v=tnq5BkcGfk0 25.09] || Simulating k-tape Turing on 1-tape. Undecidability of the Halting problem. Time and space hierarchy theorems. [https://drive.google.com/file/d/15yDi0vZVVAw-2UuBu5Mxc17KWLzSIFML/view?usp=sharing Notes] || [https://drive.google.com/file/d/1vX4cQ9nYWsetLQnZyFxTxzHQaTgJ62WL/view?usp=drive_link problem list 2] ''Update 02.10''
 
|-
 
|-
−
  || [https://www.youtube.com/watch?v=iwaqw60aZV0 ??.09] || Complexity class NP. Examples. Non-deterministic machines and another definition of NP. Polynomial reductions. NP-hardness and NP-completeness.  ||  
+
  || [https://www.youtube.com/watch?v=VR_A62kFXH8 02.10] || Complexity class NP. Examples. Non-deterministic machines and another definition of NP. Polynomial reductions. NP-hardness and NP-completeness.  || [https://drive.google.com/file/d/1SJq-s80aGYKBEtF84fz6pMYQM2ZE1UyA/view?usp=sharing problem list 3]
 
|-
 
|-
−
  || [https://www.youtube.com/watch?v=sGfulQ1YoUU ??.10] ||  NP-completenes of independent set, vertex cover, dominating set, NAE-3SAT, 3colorability. ||  
+
  || [https://www.youtube.com/watch?v=sGfulQ1YoUU 10.10] ||  NP-completenes of NAE-3SAT, 3colorability, subsetsum, knapsack, Hamiltonian cycle. Circuits: examples, class P/poly, all functions have exponential circuits. https://www.dropbox.com/scl/fi/ulrlsa5tw7kz1x0aj7bp1/circuits.pdf?rlkey=q3cx7akryx9hnsgc19yhvv0e3&dl=0 circuit_notes.pdf] || [https://drive.google.com/file/d/1KtVCvyhO99T5cU_jYLG62Zwnqj5aDCor/view?usp=sharing problem list 4]
 
|-
 
|-
−
  || [https://www.youtube.com/watch?v=Jqy89FPbFj4 ??.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. [https://www.dropbox.com/scl/fi/ulrlsa5tw7kz1x0aj7bp1/circuits.pdf?rlkey=q3cx7akryx9hnsgc19yhvv0e3&dl=0 circuit_notes.pdf] ||  
+
  || [https://www.youtube.com/watch?v=Jqy89FPbFj4 17.10] || Circuit complexity. Classes AC^i and NC^i. Some functions have exponential circuit complexity. NC1 = Boolean formulas of polynomial size. Addition in AC0. Multiplication is in NC1. P is in P/poly. 3SAT is NP-complete.  [https://www.dropbox.com/scl/fi/ulrlsa5tw7kz1x0aj7bp1/circuits.pdf?rlkey=q3cx7akryx9hnsgc19yhvv0e3&dl=0 circuit_notes.pdf] || [https://drive.google.com/file/d/15uGUYwI2GfNaEi0upjgjCqmclrWUk75c/view?usp=sharing problem list 5]
 
|-
 
|-
−
  || [https://www.youtube.com/watch?v=NNorKIxgTGU ??.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.||  
+
  || [https://youtube.com/live/kV86JYY8QXs 23.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.|| [https://drive.google.com/file/d/1-vKS0TEAD05ol2BbFpbN510TbKhucBiw/view?usp=sharing problem list 6]
 
|-
 
|-
−
  || [https://youtube.com/live/_xE0y_4Jb9o ??.11] || 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.||  
+
  || [https://youtube.com/live/W_uZuQXm53c 06.11] || 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://drive.google.com/file/d/1T9mp2AuPV2YOQ0juTMd9g0VjczHvdnSB/view?usp=sharing problem list 7]
 
|-  
 
|-  
−
|| [https://www.youtube.com/watch?v=rK5_1KPL9Ko ??.11] ||  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://youtube.com/live/ALO6r52wuIU 13.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] and [https://www.cs.cmu.edu/afs/cs/academic/class/15859-f04/www/scribes/lec2.pdf scribe1] [https://lucatrevisan.github.io/cs278-04/notes/lecture08.pdf scribe2] || [https://drive.google.com/file/d/1RlrxybN_p9X1WswJet9jpp9jPQLDYdpy/view?usp=sharing problem list 8]
 
|-
 
|-
−
  || [https://www.youtube.com/watch?v=X67F8P0dcAA ??.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.youtube.com/watch?v=X67F8P0dcAA 20.11] || Approximation algorithms. Definition c-approximation algorithm. 2-approximation for vertex cover and greedy vertex cover is not optimal. (ln n + 1)-approximation for set cover. PTAS for the makespan problem. Based on [https://www.youtube.com/watch?v=MEz1J9wY2iM&pp=ygUYYXBwcm94aW1hdGlvbiBhbGdvcml0aG1z MIT lecture].||  
 +
[https://drive.google.com/file/d/13hfO-2KUxpMnk8o0aLsJ8xO9IYfLzCHK/view?usp=sharing problem list 9]
 
|-
 
|-
−
  || [https://www.youtube.com/watch?v=f7pYWzRLflg&t=20s ??.11] || Approximation algorithms. Definition c-approximation algorithm. 2-approximation for vertex cover and greedy vertex cover is not optimal. (ln n + 1)-approximation for set cover. PTAS for the makespan problem. Based on [https://www.youtube.com/watch?v=MEz1J9wY2iM&pp=ygUYYXBwcm94aW1hdGlvbiBhbGdvcml0aG1z MIT lecture].
+
  || [https://youtube.com/live/r9rP3ZojeqY 27.11] || Parameterized complexity: The classes FPT and XP. Kernelization. Examples for vertex cover. [https://drive.google.com/file/d/1W9SU24HW0r5QhugzmrghpkzJUFuC8whq/view?usp=sharing Notes.] || [https://drive.google.com/file/d/1PpRK72BtyKYR0KVi03HDCy7HXvWpzcL6/view?usp=sharing problem list 10] <!-- [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&dl=0 programming task.] -->
−
||
+
 
|-
 
|-
−
  || ??.12 || Parameterized complexity: The classes FPT and XP. Kernelization. Examples for vertex cover. [https://www.dropbox.com/scl/fi/x5gwdae4ny4u3zixoy4pw/student_vc_branching.ipynb?rlkey=5oowq1u3jhy490s84ogojg1s7&dl=0 programming task.] [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation]. ||  
+
  || 04.12 || Parameterized complexity: W-hierarchy, hardness from the exponential time hypothesis. [https://drive.google.com/file/d/1f-085Gr7E01HepUR-brGJDet-fXJzUwb/view?usp=sharing presentation] [https://drive.google.com/file/d/1OIw7h31N2tt-npC0NrvVgNhYGw_HlJa_/view?usp=sharing Notes] || [https://drive.google.com/file/d/1xhUYMsj0iV2TMZfR8FtkxWUNlcCjdS-N/view?usp=sharing problem list 11] ''Update 05.12''
−
|-
+
−
|| ??.12 || Parameterized complexity, techniques for obtaining FPT algorithms: branching (feedback vertex), color coding (k-path problem), dynamic programming (set cover) ||
+
 
|-  
 
|-  
−
  || ??.12 || ''Colloquium'' see below for questions || [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam]  
+
  || 11.12 || ''Colloquium.'' [https://drive.google.com/file/d/1no8CbHKJluGRx7FROpSS7BqXdjOVgdT1/view?usp=sharing Rules and questions.] Version Dec 8th. [https://docs.google.com/spreadsheets/d/10zH6TVcdXWrecW8jcl57MIIq-a_Osk3-bKtPXzQIzA0/edit?usp=sharing Shedule.] || [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam]  
 +
|-
 +
|| 18.12 || ''Colloquium.'' ||
 
|}
 
|}
  
 +
Artem Perfanov's [https://drive.google.com/file/d/16_ZP0X9wwza1RsrXZZGQsx5Igwk_vY9r/view?usp=sharing lecture summaries] [https://drive.google.com/drive/folders/1XsNL2B69akd3A9qaOEgC09NiZXLP8Wbz?usp=drive_link source] (Disclaimer: I did not check them):
  
 
{| class="wikitable"
 
{| class="wikitable"
Строка 62: Строка 77:
 
!  Date !! Software engineering: parameterized complexity !! Problem list
 
!  Date !! Software engineering: parameterized complexity !! Problem list
 
|-
 
|-
−
  || ??.02 || Recap from last lecture, more examples of kernelization. ||
+
  || ??.02 || Recap from last lecture, more examples of kernels. [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 Old presentation]. ||
 
|-
 
|-
 
  || ??.02 || Linear programming kernel for vertex cover, tree decompositions ||  
 
  || ??.02 || Linear programming kernel for vertex cover, tree decompositions ||  
Строка 80: Строка 95:
 
Deadline March 31st, 23h59.  
 
Deadline March 31st, 23h59.  
  
−
<!-- The task is to understand a theoretical paper better by either
 
  
−
(Th)  Rewrite some mathematical proof of a research paper in a more accessible way using your own words. You also need to give a lecture (you are not allowed to look at the paper during the lecture). I need to work out examples. Possibly examples that I give you on the spot.
+
= Additional reading =
−
+
−
(Imp) Implement an algorithm (or parts of an algorithm) from a research paper and demonstrate that it works.
+
−
+
−
+
−
Here are examples of each type concerning the vertex cover problem:
+
  
−
(Th) prove lemma 4.1 of the paper https://epubs.siam.org/doi/pdf/10.1137/1.9781611973402.127 , you need to study some parameterized complexity, see below the table with course materials for references.  
+
Recall that the most important book for our course is ''Sipser, Introduction to the theory of computation'' 3rd edition, 2013, chapters 3, 4, 7–9. This book is intended for Bachelor students.  
  
−
(Th) prove theorem 5 from https://www.researchgate.net/profile/Lars-Jaffke/publication/329181540_What_is_known_about_Vertex_Cover_Kernelization/links/5cb319df92851c8d22ea17b6/What-is-known-about-Vertex-Cover-Kernelization.pdf
+
The following book is popular with students theoretical computer science, because it contains most materials of our course in a concise way. Moreover, it presents many important advanced topics. I find the style of some proofs rather technical, but I like the topics in this book.  
−
+
−
(Imp) implement a kernel and a simple branch and bound variant from  https://arxiv.org/pdf/1908.06795.pdf, as well as compare your algorithm with the results in the contest https://pacechallenge.org/2019/vc/vc_exact/
+
−
+
−
+
−
You can propose projects yourself, but it is not allowed to have a theoretical paper about software verification. (Because there are too many definitions, and during the lecture it usually turns out the student does not understand them.)
+
−
-->
+
  
−
= Additional reading =
+
''S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009''
  
−
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.  
+
The course materials can also be found in various chapters of the following massive book (700 pages). It starts at beginning bachelor level and ends at an advanced master level. It is written in a pleasant style with excellent examples.
  
−
C. Moore and S. Mertens, The nature of computation, 2011.  
+
''C. Moore and S. Mertens, The nature of computation, 2011.''
  
−
S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009.  
+
This book gives an introduction to important recent research directions in computational hardness. It also studies specific topics (games and planar problems) in huge detail.
  
 +
''E. Demaine, W Gasarch, Haijaghayi, Computational intractability: a guide to lower bounds, 2023'' [https://hardness.mit.edu/ current draft]
  
 
This is an advanced textbook with background on parameterized algorithms.
 
This is an advanced textbook with background on parameterized algorithms.
  
−
M. Cygan, F. Fomin and 6 others, Parameterized algorithms, 2016
+
''M. Cygan, F. Fomin and 6 others, Parameterized algorithms, 2016''
  
  
Строка 119: Строка 123:
 
  Final score = 0.35 * [score homework] + 0.35 * [score colloquium] + 0.3 * [score exam] <br>
 
  Final score = 0.35 * [score homework] + 0.35 * [score colloquium] + 0.3 * [score exam] <br>
  
−
For PI students (the course is called "computational complexity" and takes 3 modules):
+
For PI students (the course is called "computational complexity" and takes 3 modules). There are 2 scores for this course. The first one, given in December is calculated by the above formula (but it does not mean anything). The second score is given below, and it is the one that will be in the diploma. It includes a programming project. The assignment and grader, will be set up by the end of Februari, the deadline is the end of March. 
  
 
  Final score = 0.3 * [score homework] + 0.3 * [score colloquium] + 0.2 * [score exam] + 0.2 * [score project] <br>
 
  Final score = 0.3 * [score homework] + 0.3 * [score colloquium] + 0.2 * [score exam] + 0.2 * [score project] <br>
  
−
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 is applied only when the final score is transferred to the official grade. 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.
 
−
 
−
= Colloquium and exam =
 
  
−
Colloquium: in the middel of December, a list with about 20 questions will be provided. [https://www.dropbox.com/scl/fi/srv4bitahhdzcrd0vm0pr/col.pdf?rlkey=25tt9v6du6wa90tg4pn0sdn0u&dl=0 Last year's rules and questions.]
+
Some homework assignments contain extra problems. Each solution of an extra problem will give 0.5 extra points on the final exam (which is graded out of 10). There will be around 10 extra problems. Rounding is applied only when the final score is transferred to the official grade. 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.  
  
−
Exam: Copies of Sipser's book, Arora&Barak, Mertens&Moore, will be available. (I you have these books or printed parts of them, please bring it.) Also, personal handwritten notes are allowed, but nothing else.  [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam].
 
  
 
= Office hours =
 
= Office hours =
  
−
Bruno Bauwens: TBA. Better send me an email in advance.
+
Bruno Bauwens: Tuesday 12h -- 20h. Wednesday 16h -- 18h. Friday 11h -- 17h. Better send me an email in advance.
  
 
Yaroslav Ivanashev: Write in telegram.
 
Yaroslav Ivanashev: Write in telegram.

Текущая версия на 04:31, 19 декабря 2024

Classes

Lectures: Wednesdays 18h10 in Pokrovkaya room N507 and in zoom by Bruno Bauwens.

Seminars: After the lecture in room N507 and on the same zoomlink by Yaroslav Ivanashev

Telegram group for announcements and discussions invite link. The course is similar to last year's one For PI students the course is called computational complexity and has a 2nd part in Febr--March 2025.

Results.

Exam

Dec 19th 9h30 room R503.

5 or 6 questions with the same difficulty as the homework questions. You have 3 hours time.

Each year, 1 of the questions is to prove that some problem is NP-complete. Do not forget to say why the problem is in NP.

Copies of Sipser's book, Arora&Barak, Mertens&Moore, will be available. (I you have these books or printed parts of them, please bring it.) Also, personal handwritten notes are allowed, but nothing else. Sample exam.


Homeworks

Deadlines: every 2 weeks, before the lecture at 18h00. Submit in pdf or fotos of handwritten text in google classrooms. Results. Questions: Yaroslav Ivanashev.

Tasks are in the problem lists from the seminar. Deadlines: problem lists 1 and 2: at the start of 3rd lecture, lists 3 and 4 at the start of the 5th lecture, etc.

Late policy: 1 homework can be submitted at most 24h late without explanations.


Course Materials

The main reference is Sipser's book "Introduction to the theory of computation", chapters 3, 4, 7–9.

If you need some background in math, consider: Lecture notes: Discrete Mathematics, L. Lovasz, K. Vesztergombi and Лекции по дискретной математике (черновик учебника, in Russian)

Rec Summary Problem list
23.09 Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. Notes problem list 1
25.09 Simulating k-tape Turing on 1-tape. Undecidability of the Halting problem. Time and space hierarchy theorems. Notes problem list 2 Update 02.10
02.10 Complexity class NP. Examples. Non-deterministic machines and another definition of NP. Polynomial reductions. NP-hardness and NP-completeness. problem list 3
10.10 NP-completenes of NAE-3SAT, 3colorability, subsetsum, knapsack, Hamiltonian cycle. Circuits: examples, class P/poly, all functions have exponential circuits. https://www.dropbox.com/scl/fi/ulrlsa5tw7kz1x0aj7bp1/circuits.pdf?rlkey=q3cx7akryx9hnsgc19yhvv0e3&dl=0 circuit_notes.pdf] problem list 4
17.10 Circuit complexity. Classes AC^i and NC^i. Some functions have exponential circuit complexity. NC1 = Boolean formulas of polynomial size. Addition in AC0. Multiplication is in NC1. P is in P/poly. 3SAT is NP-complete. circuit_notes.pdf problem list 5
23.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 6
06.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. problem list 7
13.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 and scribe1 scribe2 problem list 8
20.11 Approximation algorithms. Definition c-approximation algorithm. 2-approximation for vertex cover and greedy vertex cover is not optimal. (ln n + 1)-approximation for set cover. PTAS for the makespan problem. Based on MIT lecture.

problem list 9

27.11 Parameterized complexity: The classes FPT and XP. Kernelization. Examples for vertex cover. Notes. problem list 10
04.12 Parameterized complexity: W-hierarchy, hardness from the exponential time hypothesis. presentation Notes problem list 11 Update 05.12
11.12 Colloquium. Rules and questions. Version Dec 8th. Shedule. Sample exam
18.12 Colloquium.

Artem Perfanov's lecture summaries source (Disclaimer: I did not check them):

Date Software engineering: parameterized complexity Problem list
 ??.02 Recap from last lecture, more examples of kernels. Old presentation.
 ??.02 Linear programming kernel for vertex cover, tree decompositions
 ??.02 hardness from ETH (exponential time hypothesis) and W-hierarchy

Recordings last year


Project (for PI students)

During the 3rd module Januari till March 2024 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.

There are 3 tasks: 2 of them about branching and kernelization, 1 task about linear programming bounds. See the table with lectures. The tasks have equal weight for the grade.

Deadline March 31st, 23h59.


Additional reading

Recall that the most important book for our course is Sipser, Introduction to the theory of computation 3rd edition, 2013, chapters 3, 4, 7–9. This book is intended for Bachelor students.

The following book is popular with students theoretical computer science, because it contains most materials of our course in a concise way. Moreover, it presents many important advanced topics. I find the style of some proofs rather technical, but I like the topics in this book.

S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009

The course materials can also be found in various chapters of the following massive book (700 pages). It starts at beginning bachelor level and ends at an advanced master level. It is written in a pleasant style with excellent examples.

C. Moore and S. Mertens, The nature of computation, 2011.

This book gives an introduction to important recent research directions in computational hardness. It also studies specific topics (games and planar problems) in huge detail.

E. Demaine, W Gasarch, Haijaghayi, Computational intractability: a guide to lower bounds, 2023 current draft

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). There are 2 scores for this course. The first one, given in December is calculated by the above formula (but it does not mean anything). The second score is given below, and it is the one that will be in the diploma. It includes a programming project. The assignment and grader, will be set up by the end of Februari, the deadline is the end of March. 

Final score = 0.3 * [score homework] + 0.3 * [score colloquium] + 0.2 * [score exam] + 0.2 * [score project]


Some homework assignments contain extra problems. Each solution of an extra problem will give 0.5 extra points on the final exam (which is graded out of 10). There will be around 10 extra problems. Rounding is applied only when the final score is transferred to the official grade. 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: Tuesday 12h -- 20h. Wednesday 16h -- 18h. Friday 11h -- 17h. Better send me an email in advance.

Yaroslav Ivanashev: Write in telegram.

Источник — «http://wiki.cs.hse.ru/index.php?title=Theory_of_Computation_2024&oldid=88671»