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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
м
 
(не показаны 102 промежуточные версии 2 участников)
Строка 1: Строка 1:
−
= Classes =
 
  
−
Lectures: Monday 13:00 - 14:20 [ zoomlink]
+
<br>
  
−
Seminars: Monday 14:40 - 16:00 [ zoomlink]
+
= Exam =
  
−
= Dates and Deadlines =
+
Date: Tuesday December 20th, 13h-16h, D501
−
Please send your homework by e-mail to both lecturers.<br>
+
  
−
= Grading =
+
The exam consists out of 8 exercises that you must solve in 3 hours time.  
−
[https://docs.google.com/spreadsheets/d/1WFBuyjv_D-8EZRhMm39fI_X69daPk2VZwzBXlchW4Mk/edit?usp=sharing Grades]
+
  
−
Colloquium: 35%<br>
+
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.
−
Homework: 35%<br>
+
−
Exam: 30%
+
  
−
== Homework Grading ==
+
Feedback exam: Friday 30.12 at 14h on [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom]
−
Some homework assignments contain extra problems. Let us call all other problems regular. The weight of each problem (whether regular or extra) in the overall homework grade is 8/''n'', where ''n'' is the total number of regular problems in all homework assignments. Partial credit is possible for some problems.
+
  
−
If you score at least 8 and solve some extra problems that do not contribute to this score, we will evaluate each of these extra problems on the scale [0, 1] and will add two maximal scores to your homework grade.
+
= Classes =
  
−
== Exam ==
+
Lectures: Monday 13:00 - 14:20 in Pokrovkaya and on zoom by [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens] and [https://www.hse.ru/en/org/persons/191486005 Alexey Talambutsa]
  
−
December 20, 9:30–12:30, [https://us02web.zoom.us/j/83533615475?pwd=WDU3cHJ5RjREOGd2YU1qdDJCVm1idz09 Zoom]
+
Seminars: Monday 14:40 - 16:00 in Pokrovkaya and on zoom by [https://www.hse.ru/en/org/persons/208499388 Pavel Zakharov]
  
−
The exam consists of 8 questions of the same level as the homework.
 
  
−
You may use all notes, books, and other reference materials. However, the solutions you submit must, of course, be your own. You are not allowed to communicate with other students and to use social network sites like Telegram, Facebook, etc. You may not use your phone except in the end of the exam to submit your work.
+
= Dates and Deadlines =
  
−
You must submit your answers in handwriting (exceptions can be asked at the beginning of the exam) by sending scanned or photographed copies to both lecturers.
+
Homeworks 1, 2, 3: <s>September 26</s>  '''October 3''' (update of 2.7 and 3.7 on 26/09)
  
−
We plan to publish the grades on December 21. If you have questions, you can ask them at 13:00 on December 21 via [https://us02web.zoom.us/j/83533615475?pwd=WDU3cHJ5RjREOGd2YU1qdDJCVm1idz09 Zoom].
+
Homeworks 4, 5: October 10
  
−
[https://youtu.be/sKYibeWX5LU Recording] of the consultation (with solutions of problems 11.7, 7.7 and 12.7)
+
Homeworks 6, 7, 8: November 7
 +
 
 +
Homeworks 9, 10, 11: November 28
 +
 
 +
Submit homework in google classroom in this [https://classroom.google.com/c/NTQ5OTYyMzk3ODc0?cjc=27kcgjp link], code: 27kcgjp  You should upload either scanned handwriting or pdf file into the corresponding section.
 +
 
 +
Table with [https://docs.google.com/spreadsheets/d/1J_mJJlr52xKDAGXF_4Rr-qdsW-q3p4XPzJVE-WDrxsk/edit?usp=sharing grades]
 +
<!-- Table with your grades: [https://docs.google.com/spreadsheets/d/126woxFOYUr2uD2FN3BEi2ACWIaJcu2TAsQTvHkRBl-s/edit?usp=sharing link].-->
  
−
Here is the [https://www.dropbox.com/s/2bt00a3fy28xwsu/exam21_12_20.pdf?dl=0 exam].
 
  
 
= Course Materials =
 
= Course Materials =
  
−
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>
 
[http://www.cs.elte.hu/~lovasz/dmbook.ps Lecture notes: Discrete Mathematics], L. Lovasz, K. Vesztergombi<br>
 
[http://www.cs.elte.hu/~lovasz/dmbook.ps Lecture notes: Discrete Mathematics], L. Lovasz, K. Vesztergombi<br>
 
[http://rubtsov.su/public/DM-HSE-Draft.pdf Лекции по дискретной математике] (черновик учебника, in Russian)
 
[http://rubtsov.su/public/DM-HSE-Draft.pdf Лекции по дискретной математике] (черновик учебника, in Russian)
 +
  
 
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-
−
! Video !! Summary !! Problem list
+
!   !! Summary !! Problem list
 
|-
 
|-
−
  || 07.09 || Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples ([https://www.dropbox.com/s/wna14b7y7nmw3cq/tm.py?dl=0 one], [https://www.dropbox.com/s/wrl3mkeqslj3xtu/wsharpw.py?dl=0 two]). Time and space complexity. Complexity classes P, PSPACE, EXP. || [https://www.dropbox.com/s/37eel2qayios6b3/prob_1.pdf?dl=0 Problem set 1]
+
  || 05.09 || Turing machines, multitape Turing machines, connection between them. Universal Turing machine. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. || [https://www.dropbox.com/s/9n9ihiti0yufvc8/prob_1.pdf?dl=0 Problem set 1]
 
|-
 
|-
−
|| 14.09 ||  Time and space hierarchy theorems. Time and space constructible functions. || [https://www.dropbox.com/s/ow4m1z8u8r211qs/prob_2.pdf?dl=0 Problem set 2]
+
|| 12.09 ||  Time and space hierarchy theorems. Time and space constructible functions. || [https://www.dropbox.com/s/jqz33aqwfl992tc/prob_2.pdf?dl=0 Problem set 2] <span style="color:red">update 26.09</span>
 
|-
 
|-
−
|| 21.09 || Complexity class NP. Examples. Polynomial reductions. NP-hardness and NP-completeness.  
+
|| 19.09 || Because of various problems, the materials of last 2 weeks were repeated. || [https://www.dropbox.com/s/05iiwsdpggfjuul/prob_3.pdf?dl=0 Problem set 3] <span style="color:red">update 25.09</span>
−
|| [https://www.dropbox.com/s/bf68zicg4uh051x/prob_03.pdf?dl=0 Problem set 3]
+
 
|-
 
|-
−
  || 28.09 || Non-deterministic TMs. Another definition of NP. Proving NP-hardness by reduction from an NP-complete problem. Examples of NP-complete problems.  || [https://www.dropbox.com/s/g817m6v0ygb8h4n/prob_04.pdf?dl=0 Problem set 4]
+
  || 26.09 || Complexity class NP. Examples. Polynomial reductions. NP-hardness and NP-completeness.  || [https://www.dropbox.com/s/454bok6rvsdtfix/prob_4.pdf?dl=0 Problem set 4]
 
|-
 
|-
−
  || 05.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.|| [https://www.dropbox.com/s/qkc5p4795rualwn/prob_05.pdf?dl=0 Problem set 5]
+
  || 3.10 || Non-deterministic TMs. Another definition of NP. Proving NP-hardness by reduction from an NP-complete problem. Examples of NP-complete problems. HAMPATH is NP-complete || [https://www.dropbox.com/s/y4ktp5e2tjryqwr/prob_5.pdf?dl=0 Problem set 5]
 
|-
 
|-
−
  || 12.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. || [https://www.dropbox.com/s/y2y1lu29936xy9n/prob_06.pdf?dl=0 Problem set 6]
+
  || 10.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. Addition in AC0. Multiplication is in NC1. [https://www.dropbox.com/s/0qnyl552qvplc0e/Acirctuis.pdf?dl=0 circuit_notes.pdf] || [https://www.dropbox.com/s/z54tjl4a5rswmhd/prob_6.pdf?dl=0 Problem set 6]
 
|-
 
|-
−
  || [https://drive.google.com/drive/folders/1loJWyo9TK6ucCp8RnD3xx3DAVPDs0OiF?usp=sharing 26.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. || [https://www.dropbox.com/s/b6m0u5vqtutdhq1/prob_07.pdf?dl=0 Problem set 7]
+
|| 17.10 || Classes L, NL, PSPACE and NPSPACE. Inclusions between P, NP, and PSPACE. Cook–Levin theorem, NP-completeness of: subsetsum, set-splitting, 3-colorability and exactly 1-in-3 SAT. || [https://www.dropbox.com/s/y8rv53yz2he58uf/prob_7.pdf?dl=0 Problem set 7]
 +
|-
 +
|| 31.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. PSPACE completeness of generalized geography. || [https://www.dropbox.com/s/d8svos0sn0d53ys/prob_08.pdf?dl=0 Problem set 8]
 
|-  
 
|-  
−
|| [https://drive.google.com/drive/folders/1w4W15sPS1nCIpQZQWasqPq8wSVLle5Ik?usp=sharing 02.11] || PSPACE completeness of generalized geography. 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/s/bvfrar2p5w3fcie/prob_08.pdf?dl=0 Problem set 8]
+
||07.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://www.dropbox.com/s/qym967max8yxhsn/prob_9.pdf?dl=0 Problem set 9]<span style="color:red">update 23.11</span>
 
|-
 
|-
−
  || 09.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/s/dciqvmire4ze4n2/prob_09.pdf?dl=0 Problem set 9]
+
  || 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 [https://www.youtube.com/watch?v=YSMgVbOqB-8&list=PLm3J0oaFux3YL5vLXpzOyJiLtqLp6dCW2&index=23 here]|| [https://www.dropbox.com/s/zg1f51ryxliz2s9/prob_10.pdf?dl=0 Problem set 10]
 
|-
 
|-
−
  || [https://youtu.be/ToxNJ9p32Ec 16.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] || [https://www.dropbox.com/s/ztg8wxuhbkhzh9e/prob_10.pdf?dl=0 Problem set 10]
+
  || 21.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] || [https://www.dropbox.com/s/r3zzgjyw07ltz2b/prob_11.pdf?dl=0 Problem set 11] <span style="color:red">update 21.11</span>
 
|-
 
|-
−
  || [https://drive.google.com/file/d/1mDd3HjabwwzNPMa7oPcnAeHRSymVmsvE/view?usp=sharing 23.11] || Finding the frequent items in streams of data: SpaceSaving and Count-Min Sketch. [https://www.dropbox.com/s/6u27au11u00n59p/tc-11-streaming.pdf?dl=0 Slides] || [https://www.dropbox.com/s/8fvpntf1n4hjoyu/prob_11.pdf?dl=0 Problem set 11]
+
  || 28.11 || More streaming algorithms: calculation F_0 moments,  Hash functions, finding the frequent items in streams of data: SpaceSaving. || [https://www.dropbox.com/s/he8ws0ldovhenhh/prob_12.pdf?dl=0 Problem set 12]
 
|-
 
|-
−
  || [https://youtu.be/H7hF07mMPzk 30.11] || Approximation algorithms. Approximate solutions for Vertex Cover, Weighted Vertex Cover, and TSP. [https://www.dropbox.com/s/wvtcsl6crkj8zeq/tc-12-approximation.pdf?dl=0 Slides.] [https://youtu.be/6ng15Bc8Dlw Seminar.]|| [https://www.dropbox.com/s/qug480ss98pq78p/prob_12.pdf?dl=0 Problem set 12]
+
  || 05.12 || Colloquium. ||  
−
+
 
|-
 
|-
−
  || 07.12 || Colloquium. ||
+
  || 12.12 || Approximation algorithms and complexity of clustering [https://www.dropbox.com/s/wvtcsl6crkj8zeq/tc-12-approximation.pdf?dl=0 Slides.]
−
|-
+
−
|| [https://www.dropbox.com/s/emvoow009xjvf5q/tc-14-clustering.pdf?dl=0 14.12] || Complexity of clustering: an exact algorithm for maximizing the inter-cluster distance and an approximate algorithm for minimizing the intra-class distance.
+
 
  || [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam]
 
  || [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam]
 
|}
 
|}
  
−
For interested students, there are 3 lectures in parameterized complexity.  
+
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.  [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 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. [https://www.mpi-inf.mpg.de/fileadmin/inf/d1/teaching/summer20/paraalg/Lectures/lecture_3.pdf  slides] from a nice [https://www.mpi-inf.mpg.de/departments/algorithms-complexity/teaching/summer20/parameterized-algorithms course]
 +
 
 +
= Project (for PI students) =
 +
 
 +
During the 3rd module Januari till March 2023. 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.
 +
 +
(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.
 +
 
 +
(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
 +
 +
(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 =
 +
 
 +
Both books contain a lot of extra materials and describe more recent discoveries in computational complexity. The first book has a gentel and pleasant style. The second book is a rigurous 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.
 +
 
 +
 
 +
= Grading =
 +
 
 +
For AMI students:
 +
 
 +
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):
 +
 
 +
Final score = 0.25 * [score homework] + 0.25 * [score colloquium] + 0.25 * [score exam] + 0.25 * [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.
 +
 
 +
 
 +
= Colloquium =
 +
 
 +
December 5, 13h00 -- 16h00, room D206 (room D102 after 14h40)
 +
 
 +
[https://www.dropbox.com/s/sk6df3zl4sxehwz/col.pdf?dl=0 rules and questions] (updated 25.11)
 +
 
 +
 
 +
 
 +
= Office hours =
  
−
14 Sept: Fixed parameter tracktability and examples, [https://www.dropbox.com/s/zzzaulpmzql7x7u/parameterizedComplexity.pdf?dl=0 presentation].
 
  
−
21 Sept: Topics from chapters 1 and 2 in "Parameterized algorithms" by Cygan, Fomin and others, 2016.
+
Bruno Bauwens: Mondays 14h30-20h. Fridays 18h-20h.  
  
−
28 Sept: The W-hierarchy, chapter 13 in the same book.
+
Alexey Talambutsa: First contact by email.

Текущая версия на 13:26, 30 декабря 2022


Exam

Date: Tuesday December 20th, 13h-16h, D501

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.

Feedback exam: Friday 30.12 at 14h on zoom

Classes

Lectures: Monday 13:00 - 14:20 in Pokrovkaya and on zoom by Bruno Bauwens and Alexey Talambutsa

Seminars: Monday 14:40 - 16:00 in Pokrovkaya and on zoom 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.

Table with grades


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. HAMPATH is NP-complete Problem set 5
10.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. Addition in AC0. Multiplication is in NC1. circuit_notes.pdf Problem set 6
17.10 Classes L, NL, PSPACE and NPSPACE. Inclusions between P, NP, and PSPACE. Cook–Levin theorem, NP-completeness of: subsetsum, set-splitting, 3-colorability and exactly 1-in-3 SAT. Problem set 7
31.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. PSPACE completeness of generalized geography. Problem set 8
07.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 set 9update 23.11
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 Problem set 10
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 Problem set 11 update 21.11
28.11 More streaming algorithms: calculation F_0 moments, Hash functions, finding the frequent items in streams of data: SpaceSaving. Problem set 12
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

Project (for PI students)

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

(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.

(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

(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

Both books contain a lot of extra materials and describe more recent discoveries in computational complexity. The first book has a gentel and pleasant style. The second book is a rigurous 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.


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.


Colloquium

December 5, 13h00 -- 16h00, room D206 (room D102 after 14h40)

rules and questions (updated 25.11)


Office hours

Bruno Bauwens: Mondays 14h30-20h. Fridays 18h-20h.

Alexey Talambutsa: First contact by email.

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