City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Probabilistic methods in computations
Saint Petersburg / spring 2012, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Randomized methods are widely used in the construction and analysis of algorithms, computational complexity theory, cryptography and in other areas of theoretical computer science. The aim of the course is to learn some of these methods and to demonstrate them on the interesting examples. The course contains lot of results from different areas of theoretical computer science, but the emphasis will be made on methods. Not all the results discussed in the course are probabilistic, the probability is sometimes used implicitly. We learn such concepts as the \( k \)-independent set of pairwise-independent hash functions, samplers, hitters, expanders, extractors, etc. The knowlege of the probability theory will be useful, although all necessary concepts and facts from the probability theory will be reminded.

Date and time Class|Name Venue|short Materials
19 February
11:15–12:50
Введение в теорию вероятностей и вероятностный метод, Lecture ПОМИ РАН video
19 February
13:00–14:35
Введение в теорию вероятностей и вероятностный метод, Lecture ПОМИ РАН video
26 February
15:35–17:10
Маленькие k-независимые множества, Lecture ПОМИ РАН video
11 March
18:30–20:05
k-независимые хеш-функции и их применения, Lecture ПОМИ РАН video
11 March
20:15–21:50
Применения хеш-функций: генерация равномерного распределения на множестве подсказок и лемма Вэлианта-Вазирани, Lecture ПОМИ РАН video
08 April
11:15–12:50
Немного смещенные распределения, Lecture ПОМИ РАН video
15 April
11:15–12:50
Немного смещенные распределения, Lecture ПОМИ РАН video
22 April
11:15–12:50
Экспандеры и блуждания по ним, Lecture ПОМИ РАН video
22 April
13:00–14:35
Сэмплеры и хиттеры, Lecture ПОМИ РАН video
29 April
11:15–12:50
Экстракторы, Lecture ПОМИ РАН video
13 May
11:15–12:50
Конструкция экстракторов. Локальная лемма Ловаса, Lecture ПОМИ РАН No
13 May
13:00–14:35
Конструктивное доказательство локальной леммы Ловаса, Lecture ПОМИ РАН video