Jakie są dobre odniesienia do zrozumienia dowodu twierdzenia PCP?

Znam wiele wyników wykorzystujących twierdzenie PCP (głównie w algorytmach aproksymacyjnych), ale nigdy nie spotkałem się z jasnym wyjaśnieniem twierdzenia PCP (tj. Że ).$\mathsf{NP} = \mathsf{PCP}(O(\log(n)),O(1))$

Jakie są dobre artykuły / książki do przeczytania?

Zarówno podręcznik złożoności Goldreicha, jak i podręcznik złożoności Arory i Baraka mają rozdziały poświęcone wyjaśnieniu dowodu twierdzenia PCP (ze zdjęciami!).

Ponadto, papier Dinur za to warto przeczytać, jeśli nie próbował go jeszcze rozwiązania. Moim zdaniem jest to co najmniej łatwiej dostępne (moim zdaniem) niż oryginalny dowód i możesz uzyskać dobrą intuicję, jak działa dowód, przeglądając tylko pierwsze 12 stron (i zagłębiam się w techniczne dowody zawarte w drugim fragmencie papieru później , Jeśli wolisz).

W 2008 roku Irit Dinur i ja prowadziliśmy kurs na PCP w Weizmann, w tym zarówno algebraiczne, jak i kombinatoryjne dowody. Odręczne notatki z wykładów są dostępne dla większości zajęć: http://people.csail.mit.edu/dmoshkov/courses/pcp/index.html

W tym semestrze prowadzę kurs PCP na MIT, który zawiera materiał ze starego kursu, bardziej kompleksowe podejście do równoległego powtarzania i unikalną hipotezę gier, a także ostatnie wyniki (z lat 2008-2009), takie jak skład i optymalizacja niskiego błędu Semidefinite Programming dla problemów z ograniczeniami związanymi z założeniem Unique Games Conjecture. Poświęcam również czas na naukę kodów korekcji błędów, ekspanderów, teorii informacji i analizy Fouriera.

To jest strona kursu: http://stellar.mit.edu/S/course/6/fa10/6.895/

Notatki są dostępne tutaj: http://people.csail.mit.edu/dmoshkov/courses/pcp-mit/index.html

Artykuł Dinura (powiązany w odpowiedzi Daniela Apona) jest dobrze napisany i wart przeczytania. Opublikowano także obszerną dyskusję na temat tego artykułu i dowodu, który jest użyteczny podczas czytania samego artykułu: Jaikumar Radhakrishnan i Madhu Sudan, On Dinur's Proof of the PCP Theorem , Bull. Amer. Matematyka Soc. 44 (2007), 19–61 ( preprint ).

Uważam, że notatki z wykładu z kursu Guruswami i O'Donnell (UW, 2005) są bardzo przydatne.

Aby zobaczyć BARDZO wysoki poziom, bardzo podobał mi się blog Tima Gowera sprzed kilku dni:

http://gowers.wordpress.com/2010/08/30/icm2010-avila-dinur-plenary-lectures/

Naprawdę pomogło mi „uzyskać” połączenie z poprawianiem błędów i niedopuszczalnością.

Rok temu był fajny samouczek na temat twierdzenia i aplikacji PCP. Notatki z wykładów powinny być pomocne: Granice algorytmów aproksymacyjnych: PCP i unikalne gry (notatki z wykładu do samouczka DIMACS)

Dla oryginalnego (i długiego) dowodu twierdzenia PCP zalecam notatki Sudanu jako podsumowanie oraz notatki z wykładu Feige, które szczegółowo wyjaśniają dowód.

Zobacz także post Fortnowa na inne materiały i przydatne dyskusje.

Proponuję przejrzeć notatki z wykładu Eli-Bena Sassona . Ponadto notatki wykładowe Prahladha Harshy zawierają i przedstawiają dowody twierdzenia PCP. Link do kursu Prahladha można znaleźć na jego stronie TIFR (U Chicago Fall 2007). Nuty kursu Venkata Guruswamiego i Ryana O'Donnella (jak sugeruje Hung Q. Ngo) są również bardzo dobre.

Są 2 źródła, które wydają mi się szczególnie dobre. Jeden, jak sugerował ktoś powyżej, to notatki z wykładów Venkata i Ryana.

Innym pomocnym źródłem są notatki z wykładów Lucy Trevisana.

Obecnie ten kurs jest oferowany w Georgia Tech przez Prasad Raghvendra. Niestety strona jeszcze nie działa.

To prowadzi mnie do innego źródła autorstwa Subhash Khot. Wyszukaj go w Google. Powinieneś być w stanie je znaleźć.

(Osobiście nie sprawdziłem też notatek Khota, ale przypomniałem sobie, że kiedyś uczył tego kursu również w GaTech)

Moja rekomendacja:

• dla początkujących informatyków:

1- Probabilistycznie sprawdzalne dowody i kody Irit Dinur

2- Dowody probabilistycznie sprawdzalne przez Madhu Sudan

3- Rozdział 9 z książki Goldreicha: Złożoność obliczeniowa, perspektywa koncepcyjna

• dla profesjonalnych informatyków:

1- Twierdzenie PCP według Gap Amplification autorstwa Irit Dinur

2- O dowodzie Dinura na twierdzenie PCP autorstwa jaikumara Radhakrishnana i Madhu Sudana

3- Rozdział 22 z książki Arora i Baraka: KOMPLEKSOWOŚĆ KOMPUTACYJNA Nowoczesne podejście

4 - Wytrzymałe PCP bliskości i krótsze PCP autorstwa Prahladha Harsha (który obejmuje pierwszy dowód na twierdzenie PCP)

Dla „klasycznego” (tj. Sprzed dinuru) dowodu twierdzenia PCP uznałem tezę Prahladha Harsha za najlepszy zasób.