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

2024-03-19T14:53:22Z

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

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

= Classes =

Lectures: Tuesday 18:10 - 19:30 in Pokrovkaya N509 and in [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom] by [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens]

Seminars: Tuesday 19:40 - 21:00 in Pokrovkaya N509 and on [https://meet.google.com/ber-yzns-hxz google.meet] by [https://www.hse.ru/en/org/persons/225553845 Nikita Lukianenko]

Telegram group for announcements and discussions [https://t.me/+foPH7ibnH1gwNjc0 invite link.] The course is similar to [http://wiki.cs.hse.ru/Theory_of_Computation_2022 last year's one]

[https://docs.google.com/spreadsheets/d/1PiivYNHnMiS9m_xeriVL82AFIcAxeDuuA85vHUMsrW8/edit?usp=sharing Results].

Note: for PI students the course is called ''computational complexity'' and has a 2nd part in Febr--March 2024.

= 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"
|-
! Rec !! Summary !! Problem list
|-
|| [https://www.youtube.com/watch?v=XcApxCiymew 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/scl/fi/p4otqrkt3v646iei0olju/prob_01.pdf?rlkey=o2m60d68oqmcivsvc1d02cz8z&dl=0 problem list 1]update 05.09
|-
|-
|| [https://www.youtube.com/watch?v=tnq5BkcGfk0 12.09] || Time and space hierarchy theorems. Time and space constructible functions. || [https://www.dropbox.com/scl/fi/c6y2bv8ur32mc725goxih/prob_02.pdf?rlkey=j7tiw1byfoipod7oys24j9fon&dl=0 problem list 2]
|-
|| [https://www.youtube.com/watch?v=iwaqw60aZV0 19.09] || Complexity class NP. Examples. Non-deterministic machines and another definition of NP. Polynomial reductions. NP-hardness and NP-completeness. || [https://www.dropbox.com/scl/fi/yz516b2b2ptptvypgl9v2/prob_03.pdf?rlkey=tljbc8bg8y44anmb7ft6j6zle&dl=0 problem list 3]
|-
|| [https://www.youtube.com/watch?v=sGfulQ1YoUU 26.09] || NP-completenes of independent set, vertex cover, dominating set, NAE-3SAT, 3colorability. || [https://www.dropbox.com/scl/fi/esjnldbdlm2fzzmro09i2/prob_04.pdf?rlkey=s2mh9i1596vrt7k27prjn0ok7&dl=0 problem list 4]update 27.09
|-
|| [https://www.youtube.com/watch?v=Jqy89FPbFj4 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. [https://www.dropbox.com/scl/fi/ulrlsa5tw7kz1x0aj7bp1/circuits.pdf?rlkey=q3cx7akryx9hnsgc19yhvv0e3&dl=0 circuit_notes.pdf] || [https://www.dropbox.com/scl/fi/mo41bviu8bhn16rm4mi8c/prob_05.pdf?rlkey=kvnv7ci0d7b9f3mef37ltg1hb&dl=0 problem list 5]update 17.10
|-
|-
|| [https://www.youtube.com/watch?v=NNorKIxgTGU 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.|| [https://www.dropbox.com/scl/fi/q2w6nkdf3fpkx7ola6xcz/prob_06.pdf?rlkey=rt75zw4nub3uuu75hsl0l76cc&dl=0 problem list 6]
|-
|| [https://youtube.com/live/_xE0y_4Jb9o 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.|| [https://www.dropbox.com/scl/fi/f5hhmvwrpark6rzeh8z7x/prob_07.pdf?rlkey=rpcmtaw54clfy3roxdev5zlio&dl=0 problem list 7]update 25.10
|-
|| [https://www.youtube.com/watch?v=rK5_1KPL9Ko 24.10] || 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/scl/fi/j8soyxc3glqiwj9ukd8mj/prob_08.pdf?rlkey=w9n8h8b3sj7uujb51d8vpos4q&dl=0 problem list 8]
|-
|| [https://www.youtube.com/watch?v=X67F8P0dcAA 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]
|-
|| [https://www.youtube.com/watch?v=f7pYWzRLflg&t=20s 14.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://www.dropbox.com/scl/fi/n6p816xwmfpugmry5x0ei/prob_10.pdf?rlkey=brvzxbz329uipvfs1i1dna61y&dl=0 problem list 10]
|-
|| [https://www.youtube.com/watch?v=GnPuhiQvs34 21.11] || Streaming algorithms I: finding the majority element, computing the sum of the last n numbers, computation of the number of different elements in logarithmic space. The median trick. Morris'es algorithm. 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/scl/fi/7aacocyfs0ccwcvtbgfua/prob_11.pdf?rlkey=62335o4b6c6d5zasq8q83j72a&dl=0 problem list 11]
|-
|| [https://www.youtube.com/watch?v=6hmQhT6ndz0 28.11] || Streaming algorithms II: Again counting different elements, see theorem 1 [https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=e3497952347101a3535434bc35d378224cf87bcc here]. Lower bounds using communication complexity. See chapt 1 in [https://arxiv.org/pdf/1509.06257.pdf Roughgarden's lecture notes]|| [https://www.dropbox.com/scl/fi/gb44vcykb3xq3b3z8z4eg/prob_12.pdf?rlkey=10541o0rr4r1a8pbys64a8vyi&dl=0 problem list 12]
|-
|| [https://www.youtube.com/watch?v=T21r8VPD3qg 05.12] || Finishing previous lecture (bounds on communication complexity). See chapt 2 in the [https://arxiv.org/pdf/1509.06257.pdf same notes] Consultation: ask anything about the course. || [https://www.dropbox.com/scl/fi/p1w8ekm265me0w75aiz0g/prob_13.pdf?rlkey=okxdhbr5jdog62y6umsb5ng9g&dl=0 problem list 13]
|-
|| 12.12 || ''Colloquium'' || [https://www.dropbox.com/s/37gdsbv2it8omnm/tc-sample-exam.pdf?dl=0 Sample exam]
|-
|| 12.19 || ''Colloquium'' (You may choose between 12-19.12) ||
|}

{| class="wikitable"
|-
! Date !! Software engineering: parameterized complexity !! Problem list
|-
|| 05.03 || 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]. || [https://www.dropbox.com/scl/fi/uijwmh01vnf5rce13ie3g/prob_p1.pdf?rlkey=0n2e5j5p7m4hpqann3pamqsrw&dl=0 problem list 14]
|-
|| 12.03 || techniques for obtaining FPT algorithms: branching (feedback vertex), color coding (k-path problem), dynamic programming (set cover) || [https://www.dropbox.com/scl/fi/aaj8o9iw5bszh3ri569rd/prob_p2.pdf?rlkey=glj4rte3bx36avwnuqgdelaj9&dl=0 problem list 15]
|-
|| 19.03 || linear programming kernel for vertex cover, tree decompositions, hardness from ETH (exponential time hypothesis) || [https://www.dropbox.com/scl/fi/pfn4pt04pko4er8mkp988/prob_p3.pdf?rlkey=ruyy67173lipbu33by31117tf&dl=0 problem list 16]
|}

[https://www.youtube.com/playlist?list=PL8EKo81hBCTGfNPpZlIe7USiEPpZGYDte Recordings]

= 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 =

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.

= Colloquium and exam =

Colloquium: on 12.12 or 19.12 at the time and place of the lecture+seminar, you can choose your time.

[https://www.dropbox.com/scl/fi/srv4bitahhdzcrd0vm0pr/col.pdf?rlkey=25tt9v6du6wa90tg4pn0sdn0u&dl=0 Rules and questions.] (Update 11.12 question 1 of part 2.)

Exam: December 27th, 10h -- 13h, room M203. Copies of Sipser's book, Arora&Barak, Mertens&Moore, chapts 1 and 2 of Roughgarden 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 =

Deadlines: every 2 weeks, before the lecture at 17h30. Submit in pdf or fotos of handwritten text in [https://classroom.google.com/c/NjIwOTk0NTM2NzE5?cjc=l4uhnyi google classrooms], code l4uhnyi. [https://docs.google.com/spreadsheets/d/1PiivYNHnMiS9m_xeriVL82AFIcAxeDuuA85vHUMsrW8/edit?usp=sharing Results]. For questions about grading, contact [https://t.me/ivanashev 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.

= Office hours =

Bruno Bauwens: Wednesdays 13h00-16h30. Fridays 14h-20h. Better send me an email in advance.

Nikita Lukianenko: Write in telegram.

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

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