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

Probabilistically checkable proofs
Saint Petersburg / autumn 2012, посмотреть все семестры

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

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

План курса:

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