Дополнительные главы теории сложности

Курс посвящен современным темам и теории сложности вычислений, которые не были освещены в базовом курсе по теории сложности.
Возможные темы:

  1. Схемная сложность.
  2. Сложность доказательств.
  3. Коммуникационная сложность.
  4. Дерандомизация вычислений.
  5. Деревья принятия решений.

Программа курса 2011 года

  1. Лекция 1. Теорема Разборова, [AB, глава 14]
  2. Лекция 2. Схемы ограниченной глубины, [AB, глава 14]
  3. Лекция 3. Теорема Разборова-Смоленского, [AB, глава 14]
  4. Лекция 4. Natural Proofs, [AB, глава 23]
  5. Лекции 5-6. PCP-теорема, [AB, глава 22]
  6. Лекция 7. Экстракторы, [AB, глава 21]
  7. Лекция 8. Дерандомизация вычислений с ограничениями по памяти, [AB, глава 21]
  8. Лекция 9. Дерандомизация не проще нижних оценок для схем, дерандомизация PIT, дерандомизация promise-MA
  9. Лекция 10. Псевдослучайный генератор Нисана-Вигдерсона, [AB, глава 20]
  10. Лекция 11. Экстрактор Тревисана [AB, глава 21]. XOR-лемма Яо, [AB, глава 19]
  11. Лекция 12. Повышение трудности с помощью кодов, [AB, глава 19]
  12. Лекции 13-14. Теорема Вильямса. [AB, Web appendix], статья Вильямса
  13. Лекция 15. Деревья принятия решений, [AB, глава 12]

Литература:

[AB] S. Arora, B. Barak, Computational Complexity: A Modern Approach. Cambridge University Press, 2009.