Theory of Computing 2019 2020 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Bbauwens (обсуждение | вклад) |
Bbauwens (обсуждение | вклад) |
||
| Строка 11: | Строка 11: | ||
Homework 1, deadline: 4 October, before the lecture <br> | Homework 1, deadline: 4 October, before the lecture <br> | ||
Homework 2, deadline: 8 November, before the lecture <br> | Homework 2, deadline: 8 November, before the lecture <br> | ||
| + | Homework 3, deadline: 6 December, before the lecture | ||
<!-- | <!-- | ||
<br> | <br> | ||
| Строка 50: | Строка 51: | ||
|| 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] | || 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] | || [https://www.dropbox.com/s/nbc2m3gama625po/prob_10.pdf?dl=0 Problem list 10] | ||
| − | |||
|- | |- | ||
| − | || | + | || 22/11 || <span style="color:red"> Communication protocols. Functions EQ, GT, DISJ, IP. Fooling sets. Combinatorial rectangles. Rectangle size lower bound. Rank lower bound. Book: [http://infotheorytcs.wikischolars.columbia.edu/file/view/Noam+Nisan+and+Eyal+Kushilevitz+-+Communication+Complexity.pdf Nisan Kushilevich: communication complexity, 1997] </span> |
| − | || [https://www.dropbox.com/s/08slc776301dhfk/prob_11.pdf?dl=0 Problem list 11] | + | || [https://www.dropbox.com/s/08slc776301dhfk/prob_11.pdf?dl=0 Problem list 11] |
|- | |- | ||
| − | || | + | || 29/11 || <span style="color:red"> 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. </span> |
|| [https://www.dropbox.com/s/3e1as6lok0h1oxw/prob_12.pdf?dl=0 Problem list 12] | || [https://www.dropbox.com/s/3e1as6lok0h1oxw/prob_12.pdf?dl=0 Problem list 12] | ||
|- | |- | ||
| − | || | + | || 6/12 || <span style="color:red"> Probabilistic versus deterministic complexity. Newman's theorem. Space-time tradeoffs for Turing machines. See Nisan Kushilevich chapters 3 and 12. Lower bound for randomized 1-shot communication complexity of set disjointness, see Roughgarden's [http://theory.stanford.edu/~tim/w15/l/l2.pdf lecture notes]). </span> |
|| [https://www.dropbox.com/s/nsa2tped7qp39ch/prob_13.pdf?dl=0 Problem list 13] | || [https://www.dropbox.com/s/nsa2tped7qp39ch/prob_13.pdf?dl=0 Problem list 13] | ||
| + | <!-- | ||
|- | |- | ||
|| 11/12 || Linear programming is in NP, NP-completeness of Hamiltonian path, TQBF as a game, PSPACE-completeness of generalized geography. Various other NP-complete problems. || [https://www.dropbox.com/s/cifs60rf6vpfn3i/prob_14.pdf?dl=0 Problem list 14] | || 11/12 || Linear programming is in NP, NP-completeness of Hamiltonian path, TQBF as a game, PSPACE-completeness of generalized geography. Various other NP-complete problems. || [https://www.dropbox.com/s/cifs60rf6vpfn3i/prob_14.pdf?dl=0 Problem list 14] | ||
Версия 12:20, 21 ноября 2019
General Information
Classes: Fridays, 15:10-18:00, R406
Dates and Deadlines
Homework 1, deadline: 4 October, before the lecture
Homework 2, deadline: 8 November, before the lecture
Homework 3, deadline: 6 December, before the lecture
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:
Lecure notes: Discrete Mathematics, L. Lovasz, K. Vesztergombi
Лекции по дискретной математике (черновик учебника, in Russian)
| Date | Summary | Problem list |
|---|---|---|
| 06.09 | Turing machines, multitape Turing machines, connection between them. Examples. Time and space complexity. Complexity classes P, PSPACE, EXP. | Problem list 1 Updated: 07.09.19 |
| 13.09 | Universal Turing machine. Space hierarchy theorem. Space constructable functions. | 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. | 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. | Problem list 4 |
| 04.10 | NP-completeness: Circuit-SAT, 3-SAT, IND-SET, BIN-INT-PROG | Problem list 5 |
| 11.10 | NP-completeness: Subset-SUM, 3COLORING. coNP, completeness of CIRC-TAUT | 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. | 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. | 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. | 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. Roughgarden's lecture notes | 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 Kushilevich: communication complexity, 1997 | Problem list 11 |
| 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. | 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. Lower bound for randomized 1-shot communication complexity of set disjointness, see Roughgarden's lecture notes). | Problem list 13 |
For interested students: lecture notes on quantum computation
Office hours
| Person | Monday | Tuesday | Wednesday | Thursday | Friday |
|---|---|---|---|---|---|
| Vladimir Podolskii, room S830 | |||||
| Bruno Bauwens, room S834 | 14-18h | 14-19h | 18-19h |
