Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Вероятностно проверяемые доказательства
Санкт-Петербург / осень 2012, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

Вероятностно проверяемые доказательства (Probabalistically Checkable Proofs или PCP) - это одно из самых ярких достижений теоретической информатики 90-х годов. PCP-теорема утверждает, что любое доказательство (в том числе математическое) можно переделать за полиномиальное время в такое, которое можно вероятностно проверить, прочитав лишь константное число битов этого доказательства, при этом алгоритм проверки доказательства использует лишь логарифмическое число случайных битов. Утверждение PCP-теоремы интересно и само по себе, но оно имеет важнейшее применение в теории приближенных алгоритмов для оптимизационных задач. Для многих оптимизационных задач с помощью PCP-теоремы было найдено точное значение параметра с, что существует c-приближенный полиномиальный алгоритм, но для всех c'>c существование c'-приближенного алгоритма влечет P=NP. В курсе планируется подробно разобраться со всей используемой техникой и полностью доказать PCP-теорему и ее усиленные варианты, используемые в приложениях.

План курса:

  • Доказательство PCP-теоремы, придуманное Динур.
  • 3-х битная версия PCP-теоремы Хастада и следствия про трудность приближения.
  • Unique Game Conjecture - гипотеза, к которой сводятся очень многие вопросы о существовании приближенного алгоритма.
Дата и время Занятие Место Материалы
07 октября
11:15–12:50
Вероятностно проверяемые доказательства и приближенные алгоритмы, Лекция ПОМИ РАН Нет
07 октября
13:00–14:35
Экспоненциальная PCP-теорема, Лекция ПОМИ РАН Нет
14 октября
11:15–12:50
Доказательство PCP теоремы (начало), Лекция ПОМИ РАН Нет
14 октября
13:00–14:35
Доказательство PCP теоремы (продолжение), Лекция ПОМИ РАН Нет
28 октября
11:15–12:50
Доказательство PCP теоремы (продолжение), Лекция ПОМИ РАН Нет
28 октября
13:00–14:35
Доказательство PCP теоремы (окончание), Лекция ПОМИ РАН Нет
04 ноября
11:15–12:45
3-битная PCP-теорема Хастада, Лекция ПОМИ РАН Нет
04 ноября
13:00–14:35
3-битная PCP-теорема Хастада (продолжение), Лекция ПОМИ РАН Нет
18 ноября
13:00–14:35
Неприближаемость задачи о покрытии множествами, Лекция ПОМИ РАН Нет
25 ноября
11:15–12:50
О доказательстве Теоремы Раза о параллельном повторении. Unique Game Conjecture., Лекция ПОМИ РАН Нет
25 ноября
13:00–14:35
Неприближаемость задачи MAXCut, Лекция ПОМИ РАН Нет
02 декабря
11:15–12:50
Неприближаемость задач о кодах, Лекция ПОМИ РАН Нет