Теория сложности вычислений и доп. главы дискретной математики

Задачи

Лекция 1. Теорема Разборова, [AB, глава 14], слайды

Лекция 2. Схемы ограниченной глубины, [AB, глава 14], слайды

Лекция 3. Теорема Разборова-Смоленского, [AB, глава 14], слайды

Лекция 4. Natural Proofs, [AB, глава 23], слайды

Лекции 5-6. PCP-теорема, [AB, глава 22]

Лекция 7. Экстракторы, [AB, глава 21], слайды

Лекция 8. Дерандомизация вычислений с ограничениями по памяти, [AB, глава 21], слайды

Лекция 9. Дерандомизация не проще нижних оценок для схем, дерандомизация PIT, дерандомизация promise-MA

Лекция 10. Псевдослучайный генератор Нисана-Вигдерсона, [AB, глава 20], слайды

Лекция 11. Экстрактор Тревисана [AB, глава 21]. XOR-лемма Яо, [AB, глава 19], слайды

Лекция 12. Повышение трудности с помощью кодов, [AB, глава 19], слайды

Лекции 13-14. Теорема Вильямса. [AB, Web appendix], статья Вильямса

Лекция 15. Деревья принятия решений, [AB, глава 12]