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

Computational Complexity Theory
Saint Petersburg / autumn 2021, посмотреть все семестры

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

TBD

Date and time Class|Name Venue|short Materials
14 September
18:30–19:50
Лекция 1. Машины Тьюринга и булевы схемы, Lecture Конференция в zoom, Онлайн slides,  video
14 September
20:00–21:20
Семинар 1, Seminar Конференция в zoom, Онлайн
21 September
18:30–19:50
Лекция 2. Класс NP, недетерминированные машины Тьюринга., Lecture Конференция в zoom, Онлайн slides,  video
21 September
20:00–21:20
Семинар 2, Lecture Конференция в zoom, Онлайн
28 September
18:30–19:50
Лекция 3. Теорема Кука-Левина, задачи поиска, Lecture Конференция в zoom, Онлайн slides,  video
28 September
20:00–21:20
Семинар 3, Lecture Конференция в zoom, Онлайн
05 October
18:30–19:50
Лекция 4. Между P и NP., Lecture Конференция в zoom, Онлайн slides,  video
05 October
20:00–21:20
Семинар 4, Lecture Конференция в zoom, Онлайн
12 October
18:30–19:50
Лекция 5. Вычисления с ограничениями по памяти., Lecture Конференция в zoom, Онлайн slides,  video
12 October
20:00–21:20
Семинар 5, Lecture Конференция в zoom, Онлайн
19 October
18:30–19:50
Лекция 6. Логарифмическая память, Lecture Конференция в zoom, Онлайн slides,  video
19 October
20:00–21:20
Семинар 6, Seminar Конференция в zoom, Онлайн
26 October
18:30–19:50
Лекция 7. Полиномиальная иерархия, Lecture Конференция в zoom, Онлайн slides,  video
26 October
20:00–21:20
Семинар 7, Seminar Конференция в zoom, Онлайн
02 November
18:30–19:50
Лекция 8. Вычисления с ограниченим и по времени, и по памяти. Схемная сложность., Lecture Конференция в zoom, Онлайн slides,  video
02 November
20:00–21:20
Семинар 8, Seminar Конференция в zoom, Онлайн
09 November
18:30–19:50
Лекция 9. Вероятностные классы сложности., Lecture Конференция в zoom, Онлайн slides,  video
09 November
20:00–21:20
Семинар 9, Seminar Конференция в zoom, Онлайн
16 November
18:30–19:50
Лекция 10. Интерактивные доказательства, Lecture Конференция в zoom, Онлайн slides,  video
16 November
20:00–21:20
Семинар 10, Seminar Конференция в zoom, Онлайн
23 November
18:30–19:50
Лекция 11. Вероятностно-проверяемые доказательства, Lecture Конференция в zoom, Онлайн slides,  video
23 November
20:00–21:20
Семинар 11, Seminar Конференция в zoom, Онлайн
30 November
18:30–19:50
Лекция 12. Вероятностно-проверяемые доказательства, окончание, Lecture Конференция в zoom, Онлайн slides,  video
30 November
20:00–21:20
Семинар 12, Seminar Конференция в zoom, Онлайн