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

2019-12-18T15:09:04Z

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

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

== General Information ==

Classes: Fridays, 15:10-18:00, R406

[https://www.dropbox.com/s/suzbqo0k37blw2b/grading.pdf?dl=0 Grading]

[https://docs.google.com/spreadsheets/d/12KPgGxfFTZNrBse0JPnh1Jdd4cFpJBGCD_37YszaJ8I/edit?usp=sharing Homework results]

== Dates and Deadlines ==

Homework 1, deadline: 4 October, before the lecture 
Homework 2, deadline: 8 November, before the lecture 
Homework 3, deadline: 8 December, 2 days extension

== Colloquium ==

Date and time: December 13, 15:10 
Room: R405 
[https://www.dropbox.com/s/rbjd1hsuhtbmvzq/col.pdf?dl=0 Program] Updated: 11.12.19 (question 7 of part 2 is removed)

== Course Materials ==

In the first 10 lectures, we follow Sipser's book "Introduction to the theory of computation" Chapters 7, 8, 9 (not Theorem 9.15), and Section 10.2.

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

{| class="wikitable"
|-
! Date !! Summary !! Problem list
|-
|| 06.09 || Turing machines, multitape Turing machines, connection between them. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. || [https://www.dropbox.com/s/lxoenwqohopsoca/prob_1.pdf?dl=0 Problem list 1 ] Updated: 07.09.19
|-
|| 13.09 || Universal Turing machine. Space hierarchy theorem. Space constructable functions. || [https://www.dropbox.com/s/vs07m4iaepi64ao/prob_2.pdf?dl=0 Problem list 2]
|-
|| 20.09 || Complexity class NP. Examples. Inclusions between P, NP and PSPACE. Non-deterministic TMs. Another definition of NP. Polynomial reductions, their properties. NP-hardness and NP-completeness, their properties. || [https://www.dropbox.com/s/3yu3xtdgigugkaw/prob_3.pdf?dl=0 Problem list 3 ]
|-
|| 27.09 || 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/zn5n3gihxrb1gko/prob_4.pdf?dl=0 Problem list 4]
|-
|| 04.10 || NP-completeness: Circuit-SAT, 3-SAT, IND-SET, BIN-INT-PROG || [https://www.dropbox.com/s/gfdnexki0dfj3g0/prob_5.pdf?dl=0 Problem list 5]
|-
|| 11.10 || NP-completeness: Subset-SUM, 3COLORING. coNP, completeness of CIRC-TAUT || [https://www.dropbox.com/s/qa2t7bm7lmw6rbe/prob_6.pdf?dl=0 Problem list 6]
|-
|| 18.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 constructable s. || [https://www.dropbox.com/s/nllomqsrocqcjcv/prob_7.pdf?dl=0 Problem list 7]
|-
|| 01.11 || PSPACE-completeness of formula game and generalized geography. Oracle computation definitions. There exists a language A for which P^A = NP^A. || [https://www.dropbox.com/s/e5ccevcu9ig23lu/prob_8.pdf?dl=0 Problem list 8]
|-
|| 08.11 || There is an oracle B such that P^B is not equal to NP^B. Probabilistic computation. Probabilistic machines, the class BPP, invariance of the definition BPP for different thresholds, RP, coRP, PP, ZPP. || [https://www.dropbox.com/s/36ov36op8wvkdf7/prob_9.pdf?dl=0 Problem list 9]
|-
|| 15/11 || Streaming algorithms: finding the majority element, computation of the moment F_2 in logarithmic space, lower-bound for exact and probabilistic computation of F_0 using one-shot communication complexity. [http://theory.stanford.edu/~tim/w15/l/l1.pdf Roughgarden's lecture notes]
|| [https://www.dropbox.com/s/nbc2m3gama625po/prob_10.pdf?dl=0 Problem list 10]
|-
|| 22/11 || Communication protocols. Functions EQ, GT, DISJ, IP. Fooling sets. Combinatorial rectangles. Rectangle size lower bound. Rank lower bound. Book: Nisan and Kushilevich: communication complexity, 1997 [https://epdf.pub/communication-complexity.html download]
|| [https://www.dropbox.com/s/zn0nn6rzxvyjtwd/prob_11.pdf?dl=0 Problem list 11] Updated HW-problem: 22.11.19
|-
|| 29/11 || Nondeterministic communication complexity. D(f) < O(N^0(f) N^1(f)). Deterministic complexity vs number of leafs in a protocol tree. Randomized communication complexity: definitions. Functions EQ, GT, MCE. Newman's theorem (only the statement)
|| [https://www.dropbox.com/s/km4wkungoh0qplt/prob_12.pdf?dl=0 Problem list 12]
|-
|| 6/12 || Probabilistic versus deterministic complexity. Newman's theorem. Space-time tradeoffs for Turing machines. See Nisan Kushilevich chapters 3 and 12.
|| [https://www.dropbox.com/s/daj8me2wtt7b5eg/prob_13.pdf?dl=0 Problem list 13]
|-
|| 20/12 || Questions from students about exercises and homework. Poly time reductions on graphs and NP-completeness of Hamiltonion graphs. (If interested, one-shot complexity of the disjointness problem, this is not for the exam.) Solving [http://www.mi-ras.ru/~podolskii/files/computability1819/exam171222.pdf the exam of 2 years ago].
||

|}

For interested students: [https://homepages.cwi.nl/~rdewolf/qcnotes.pdf lecture notes on quantum computation]

== Office hours ==

{| class="wikitable"
|-
! Person !! Monday !! Tuesday !! Wednesday !! Thursday !! Friday
|-
| Vladimir Podolskii, room S830 || || || || ||
|-
| Bruno Bauwens, room S834 || || || 14-18h || || 18-19h
|}

Theory of Computing 2019 2020 - История изменений

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