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

Bbauwens в 18:38, 18 декабря 2018

2018-12-18T18:38:03Z

← Предыдущая версия		Версия от 18:38, 18 декабря 2018
Строка 26:		Строка 26:
	== Course Materials ==		== Course Materials ==

	[http://www.mi.ras.ru/~podolskii/files/computability1819/exam171222.pdf Last year exam]		<span style="color:red">New</span> [http://www.mi.ras.ru/~podolskii/files/computability1819/exam171222.pdf Last year exam]

	{\| class="wikitable"		{\| class="wikitable"
Строка 67:		Строка 67:
	\|\| 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]
	\|-		\|-
	\|\| 18/12 \|\| Questions from students about exercises and homework. Kolmogorov complexity, symmetry of information~~, information distance~~. [Optional lecture, not for the exams.] \|\|		\|\| 18/12 \|\| Questions from students about exercises and homework. Kolmogorov complexity, symmetry of information. [Optional lecture, not for the exams.] \|\| [https://www.dropbox.com/s/b3g60wwwbqpmotm/prob_15.pdf?dl=0 Problem list 15]
	\|}		\|}

Vpodolskii в 11:35, 18 декабря 2018

2018-12-18T11:35:55Z

← Предыдущая версия		Версия от 11:35, 18 декабря 2018
Строка 26:		Строка 26:
	== Course Materials ==		== Course Materials ==

			[http://www.mi.ras.ru/~podolskii/files/computability1819/exam171222.pdf Last year exam]

	{\| class="wikitable"		{\| class="wikitable"

Bbauwens в 13:19, 17 декабря 2018

2018-12-17T13:19:13Z

← Предыдущая версия		Версия от 13:19, 17 декабря 2018
Строка 66:		Строка 66:
	\|\| 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]
	\|-		\|-
	\|\| 18/12 \|\| Questions from students about exercises and homework. Kolmogorov complexity, symmetry of information, information distance. [Optional lecture, not for the exams. \|\|		\|\| 18/12 \|\| Questions from students about exercises and homework. Kolmogorov complexity, symmetry of information, information distance. [Optional lecture, not for the exams.] \|\|
	\|}		\|}

Bbauwens в 13:18, 17 декабря 2018

2018-12-17T13:18:49Z

← Предыдущая версия		Версия от 13:18, 17 декабря 2018
Строка 65:		Строка 65:
	\|-		\|-
	\|\| 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]
			\|-
			\|\| 18/12 \|\| Questions from students about exercises and homework. Kolmogorov complexity, symmetry of information, information distance. [Optional lecture, not for the exams. \|\|
	\|}		\|}

Bbauwens в 15:29, 11 декабря 2018

2018-12-11T15:29:00Z

← Предыдущая версия		Версия от 15:29, 11 декабря 2018
Строка 64:		Строка 64:
	\|\| [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, 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]
	\|}		\|}

Bbauwens в 15:28, 11 декабря 2018

2018-12-11T15:28:08Z

← Предыдущая версия		Версия от 15:28, 11 декабря 2018
Строка 63:		Строка 63:
	\|\| 4/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 [http://theory.stanford.edu/~tim/w15/l/l2.pdf lecture notes]).		\|\| 4/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 [http://theory.stanford.edu/~tim/w15/l/l2.pdf lecture notes]).
	\|\| [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, PSPACE-completeness of generalized geography. Various other NP-complete problems. \|\| [https://www.dropbox.com/s/cifs60rf6vpfn3i/prob_14.pdf?dl=0 Problem list 14]
	\|}		\|}

Bbauwens в 14:09, 4 декабря 2018

2018-12-04T14:09:33Z

@@ Строка 61: / Строка 61: @@
   || [https://www.dropbox.com/s/3e1as6lok0h1oxw/prob_12.pdf?dl=0 Problem list 12]
 |-
-  || 4/12 || Probabilistic versus deterministic complexity. Newman's theorem. Space-time tradeoffs for Turing machines. Lower bound for randomized 1-shot communication complexity of set disjointness (see Roughgarden's lecture notes).
+  || 4/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 [http://theory.stanford.edu/~tim/w15/l/l2.pdf lecture notes]).
   || [https://www.dropbox.com/s/nsa2tped7qp39ch/prob_13.pdf?dl=0 Problem list 13]
 |}

Bbauwens в 14:04, 4 декабря 2018

2018-12-04T14:04:37Z

@@ Строка 60: / Строка 60: @@
   || 27/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.
   || [https://www.dropbox.com/s/3e1as6lok0h1oxw/prob_12.pdf?dl=0 Problem list 12]
 <!--
 |-
   || Randomized communication complexity of IP. Streaming algorithms. Finding the majority element. Deciding whether there is a most frequent element is hard. One-sided probabilistic complexity of disjointness.

Bbauwens в 09:35, 28 ноября 2018

2018-11-28T09:35:50Z

← Предыдущая версия		Версия от 09:35, 28 ноября 2018
Строка 57:		Строка 57:
	\|\| 20/11 \|\| 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]		\|\| 20/11 \|\| 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]
	\|\| [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]
			\|-
			\|\| 27/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.
			\|\| [https://www.dropbox.com/s/3e1as6lok0h1oxw/prob_12.pdf?dl=0 Problem list 12]
	<!--		<!--
	\|-		\|-

Vpodolskii в 21:53, 26 ноября 2018

2018-11-26T21:53:27Z

← Предыдущая версия		Версия от 21:53, 26 ноября 2018
Строка 22:		Строка 22:
	Date and time: December 10, 16:40<br>		Date and time: December 10, 16:40<br>
	Room: 400 <br>		Room: 400 <br>
			[http://www.mi.ras.ru/~podolskii/files/computability1819/col.pdf Program]

	== Course Materials ==		== Course Materials ==