Вероятностно проверяемые доказательства

Общая информация
ЛекторД. М. Ицыксон
Семестросень 2012
Дата начала07.10.2012
Количество пар12
Язык курсарусский
Вопросы к экзамену
Анонсы
Встреча ВКонтактеhttp://vk.com/probcheckproofs
Встреча на сайте T&Phttp://theoryandpractice.ru/courses/11332-veroyatnostno-proveryaemye-dokazatelst...
Анонс habrahabr.ruhttp://habrahabr.ru/events/1034/
Аннотация

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

План курса:

  • Доказательство PCP-теоремы, придуманное Динур.
  • 3-х битная версия PCP-теоремы Хастада и следствия про трудность приближения.
  • Unique Game Conjecture - гипотеза, к которой сводятся очень многие вопросы о существовании приближенного алгоритма.

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Вероятностно проверяемые доказательства и приближенные алгоритмы
(07.10.2012 - 11:15 - 12:50)

Приближенные алгоритмы для MAX3SAT, вершинного покрытия. Класс PCP(r(n),q(n)), формулировка PCP-теоремы, эквивалентность PCP-теоремы и NP-трудности задачи $ \rho $-GAP-q-CSP, связь с трудностью приближения. Переформулировка для $ \rho $-GAP-3-SAT. http://www.lektorium.tv/lecture/?id=13982
2. Экспоненциальная PCP-теорема
(07.10.2012 - 13:00 - 14:35)

Отсутствие константного приближения для задачи о независимом множестве. Коды Уолша-Адамара, их локальное декодирование. Тестирование функции на линейность. $ NP\subseteq PCP(poly(n),1) $. http://www.lektorium.tv/lecture/?id=13983
3. Доказательство PCP теоремы (начало)
(14.10.2012 - 11:15 - 12:50)

Тестирование функции на линейность с помощью базиса Фурье. Общий план доказательства PCP-теоремы. Понижение алфавита (начало). http://www.lektorium.tv/lecture/?id=14002
4. Доказательство PCP теоремы (продолжение)
(14.10.2012 - 13:00 - 14:35)

Понижение алфавита (окончание). Алгебраические экспандеры. Лемма о перемешивании, следствия. Повышение зазора: Сведение к арности 2. http://www.lektorium.tv/lecture/?id=14003
5. Доказательство PCP теоремы (продолжение)
(28.10.2012 - 11:15 - 12:50)

Повышение зазора: сведение к d-регулярному экспандеру. Описание основного сведения. http://www.lektorium.tv/lecture/?id=14046
6. Доказательство PCP теоремы (окончание)
(28.10.2012 - 13:00 - 14:35)

Повышение зазора: анализ основной конструкции. http://www.lektorium.tv/lecture/?id=14047
7. 3-битная PCP-теорема Хастада
(04.11.2012 - 11:15 - 12:45)

3-битная PCP-теорема, приближение задач MAX3XORSAT и MAX3SAT. Формулировка теоремы Раза. Длинные коды. Тест на длинный код.
8. 3-битная PCP-теорема Хастада (продолжение)
(04.11.2012 - 13:00 - 14:35)

Тест Хастада и его анализ.
9. Неприближаемость задачи о покрытии множествами
(18.11.2012 - 13:00 - 14:35)

Неприближаемость задачи о покрытии множествами с константным множителем. Конструкция (k,l)-set gadget. Неприближаемость с логарифмическим множителем. http://www.lektorium.tv/lecture/?id=14097
10. О доказательстве Теоремы Раза о параллельном повторении. Unique Game Conjecture.
(25.11.2012 - 11:15 - 12:50)

О доказательстве теоремы Раза о параллельном повторении. Unique Game Conjecture. Неприближаемость задачи о максимальном разрезе при UGC. Конструкция сведения. http://www.lektorium.tv/lecture/?id=14116
11. Неприближаемость задачи MAXCut
(25.11.2012 - 13:00 - 14:35)

Тест на устойчивость. Формулировка теоремы о Majority is Stablest. Анализ сведения задачи о максимальном разрезе к UGC. http://www.lektorium.tv/lecture/?id=14117
12. Неприближаемость задач о кодах
(02.12.2012 - 11:15 - 12:50)

Неприближаемость задачи о ближайшем кодовом слове. Коды БЧХ. Неприближаемость задачи о минимальном кодовом расстоянии.
Ваша оценка: Пусто Средняя: 4.2 (6 votes)
Share |