Jakie są dobre odniesienia do zrozumienia dowodu twierdzenia PCP?


64

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 ).NP=PCP(O(log(n)),O(1))

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

Odpowiedzi:


40

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).


3
Właściwie wolę pracę Dinura od dyskusji w Arora / Barak.
András Salamon

37

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


1
Fajnie, to są świetne nuty. Tak naprawdę cieszę się, że wreszcie mogę zobaczyć autora dołączonego do „Ilustrowanej historii twierdzenia PCP”. Widziałem to wcześniej w wielu miejscach, ale nigdy nie podano źródła!
Daniel Apon,

23

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 ).






12

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.


12

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)


11

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)


8

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

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.