imported>Bbauwens: Migrated current public revision from wiki.cs.hse.ru

2022-12-30T10:26:54Z

Migrated current public revision from wiki.cs.hse.ru

Новая страница

= 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 [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom]

= Classes =

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]

Seminars: Monday 14:40 - 16:00 in Pokrovkaya and on zoom by [https://www.hse.ru/en/org/persons/208499388 Pavel Zakharov]

= Dates and Deadlines =

Homeworks 1, 2, 3: <s>September 26</s> '''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 [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]


= 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 [http://wiki.cs.hse.ru/Theory_of_Computation_2021 previous year].

If you need some background in math, consider these two sources: 
[http://www.cs.elte.hu/~lovasz/dmbook.ps Lecture notes: Discrete Mathematics], L. Lovasz, K. Vesztergombi 
[http://rubtsov.su/public/DM-HSE-Draft.pdf Лекции по дискретной математике] (черновик учебника, in Russian)

{| class="wikitable"
|-
! !! 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. || [https://www.dropbox.com/s/9n9ihiti0yufvc8/prob_1.pdf?dl=0 Problem set 1]
|-
|| 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] update 26.09
|-
|| 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] update 25.09
|-
|| 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]
|-
|| 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]
|-
|| 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]
|-
|| 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]
|-
||07.11 || Oracle computation definitions. There exists an oracle ''A'' for which P''A'' = NP''A''. There is an oracle B such that P''B'' is not equal to NP''B''. || [https://www.dropbox.com/s/qym967max8yxhsn/prob_9.pdf?dl=0 Problem set 9]update 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 [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]
|-
|| 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 [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] update 21.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]
|-
|| 05.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/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 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. [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] 

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)

[https://www.dropbox.com/s/sk6df3zl4sxehwz/col.pdf?dl=0 rules and questions] (updated 25.11)

= Office hours =

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

Alexey Talambutsa: First contact by email.

Theory of Computation 2022 - История изменений

imported>Bbauwens: Migrated current public revision from wiki.cs.hse.ru