Каковы хорошие ссылки на понимание доказательства теоремы PCP?
64
Я знаком со многими результатами, в которых используется теорема PCP (главным образом в приближенных алгоритмах), но я никогда не сталкивался с четким объяснением теоремы PCP (то есть, что ).N P = P C P (O(log( н ) ) , O ( 1 ) )
Какие хорошие бумаги / книги для этого нужно прочитать?
Кроме того, статью Динура стоит прочитать, если вы еще не пытались ее решить. Это, по крайней мере, более доступно (на мой взгляд), чем оригинальное доказательство, и вы можете получить хорошую интуицию о том, как доказательство работает, просматривая только первые 12 страниц (и углубившись в технические доказательства, содержащиеся в последнем куске статьи позже , если хочешь).
На самом деле я предпочитаю статью Динура обсуждению в Арора / Барак.
Андрас Саламон
37
В 2008 году мы с Иритом Динуром провели курс по PCP в Weizmann, включая как алгебраические, так и комбинаторные доказательства. Рукописные конспекты доступны для большинства классов:
http://people.csail.mit.edu/dmoshkov/courses/pcp/index.html
В этом семестре я преподаю курс PCP в Массачусетском технологическом институте, который содержит материал старого курса, более всестороннюю трактовку параллельного повторения и гипотезу об уникальных играх, а также последние результаты (с 2008-2009 гг.), Такие как низкий состав ошибок и оптимальность полуопределенного программирования для проблем удовлетворения ограничений, предполагающих гипотезу об уникальных играх. Я также посвящаю время обучению исправлению ошибок, расширителям, теории информации и анализу Фурье.
Круто, это отличные заметки. Я на самом деле рад наконец увидеть автора, прикрепленного к «Иллюстрированной истории теоремы PCP». Я видел это несколько раз прежде, но никогда с цитируемым источником!
Даниэль Апон
23
Статья Динура (на которую ссылается Даниэль Апон) написана хорошо и заслуживает прочтения Также была опубликована расширенная дискуссия об этой статье и доказательстве, что полезно при чтении самой статьи: Джайкумар Радхакришнан и Мадху Судан, «Доказательство Динура о теореме PCP» , Bull. Amer. Математика Soc. 44 (2007), 19-61 ( препринт ).
Для оригинального (и длинного) доказательства теоремы PCP я рекомендую заметки Судана в качестве резюме и примечания к лекции Фейджа, которые подробно объясняют это доказательство.
Кроме того, см. Сообщение Fortnow для других материалов и полезных обсуждений.
Я бы предложил просмотреть конспект лекций Эли-Бена Сассона . Кроме того, лекционные заметки Прахлада Харши содержат и излагают оба доказательства теоремы PCP. Ссылку на курс Прахлада можно найти на его веб-странице TIFR (U Chicago Fall 2007). Заметки о курсе Венката Гурусвами и Райана О'Доннелла (как предположил Хунг В. Нго) тоже очень хороши.
В 2008 году мы с Иритом Динуром провели курс по PCP в Weizmann, включая как алгебраические, так и комбинаторные доказательства. Рукописные конспекты доступны для большинства классов: http://people.csail.mit.edu/dmoshkov/courses/pcp/index.html
В этом семестре я преподаю курс PCP в Массачусетском технологическом институте, который содержит материал старого курса, более всестороннюю трактовку параллельного повторения и гипотезу об уникальных играх, а также последние результаты (с 2008-2009 гг.), Такие как низкий состав ошибок и оптимальность полуопределенного программирования для проблем удовлетворения ограничений, предполагающих гипотезу об уникальных играх. Я также посвящаю время обучению исправлению ошибок, расширителям, теории информации и анализу Фурье.
Это веб-сайт курса: http://stellar.mit.edu/S/course/6/fa10/6.895/
Примечания доступны здесь: http://people.csail.mit.edu/dmoshkov/courses/pcp-mit/index.html
источник
Статья Динура (на которую ссылается Даниэль Апон) написана хорошо и заслуживает прочтения Также была опубликована расширенная дискуссия об этой статье и доказательстве, что полезно при чтении самой статьи: Джайкумар Радхакришнан и Мадху Судан, «Доказательство Динура о теореме PCP» , Bull. Amer. Математика Soc. 44 (2007), 19-61 ( препринт ).
источник
Я нашел лекционные заметки из курса Guruswami & O'Donnell (UW, 2005) очень полезными.
источник
Для ОЧЕНЬ высокого уровня мне очень понравилось сообщение в блоге Тима Гауэра несколько дней назад:
http://gowers.wordpress.com/2010/08/30/icm2010-avila-dinur-plenary-lectures/
Действительно помог мне "получить" связь с кодами, исправляющими ошибки, и с неприемлемостью.
источник
Год назад было хорошее руководство по теореме и приложениям PCP. Их лекционные заметки должны быть полезны: Пределы алгоритмов приближения: PCP и уникальные игры (Учебные заметки DIMACS)
источник
Для оригинального (и длинного) доказательства теоремы PCP я рекомендую заметки Судана в качестве резюме и примечания к лекции Фейджа, которые подробно объясняют это доказательство.
Кроме того, см. Сообщение Fortnow для других материалов и полезных обсуждений.
источник
Я бы предложил просмотреть конспект лекций Эли-Бена Сассона . Кроме того, лекционные заметки Прахлада Харши содержат и излагают оба доказательства теоремы PCP. Ссылку на курс Прахлада можно найти на его веб-странице TIFR (U Chicago Fall 2007). Заметки о курсе Венката Гурусвами и Райана О'Доннелла (как предположил Хунг В. Нго) тоже очень хороши.
источник
Есть 2 источника, которые кажутся мне особенно хорошими. Один из них, как предлагал кто-то из вышеупомянутых, - это лекционные записи Венката и Райана
Другой полезный источник - это лекционные заметки Луки Тревизана.
В настоящее время этот курс предлагается в Georgia Tech Прасадом Рагхвендрой. К сожалению, страница еще не открыта.
Это подводит меня к другому источнику от Субхаша Хота. Ищите его в Google. Вы должны быть в состоянии найти их.
(Лично я тоже не просматривал заметки Хота, но просто вспомнил, что он когда-то преподавал этот курс и в GaTech)
источник
Моя рекомендация:
1- Вероятностно проверяемые доказательства и коды Ирит Динур
2- Вероятностно проверяемые доказательства Мадху Судан
3- Глава 9 из книги Гольдрайха: вычислительная сложность, концептуальная перспектива
1- Теорема PCP по усилению разрыва Иритом Динуром
2- О доказательстве Динура теоремы PCP Джайкумара Радхакришнана и Мадху Судана
3- Глава 22 из книги Арора и Барак: ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ Современный подход
4- Надежные РСР Близких и Коротких РСР от Prahladh Harsha (который охватывает первое доказательство терема PCP)
источник
Для «классического» (т. Е. Доинурского) доказательства теоремы PCP я нашел тезис Прахлада Харши лучшим источником.
источник