Dobre przykłady, jak dobrze pisać w TCS

Redagowałem manuskrypt studencki. Uczeń zauważył, że miło byłoby zobaczyć przykłady dobrej jakości pisania w opublikowanych pracach i zdałem sobie sprawę, że tak naprawdę nie mogę wymyślić dobrych przykładów z głowy

Jakie są najlepsze przykłady wysokiej jakości pisania matematycznego, jakie widziałeś?

Zasady:

• Wolę papiery TCS, o ile to możliwe. Nasz styl różni się na tyle od standardowych artykułów matematycznych, że myślę, że lepiej skupić się na TCS (również dlaczego pytam tutaj, a nie MO)
• pomogłoby to, gdybyś wspomniał o tym, co dokładnie uważałeś za dobre. Nie każda ekspozycja jest dobra we wszystkim - niektóre papiery mają świetne kontury dowodów, niektóre używają notacji naprawdę skutecznie, a inne mistrzowsko przekazują intuicję.
• jeśli to możliwe, proszę link do artykułu.

Mam nadzieję, że stanie się to zasobem, podobnie jak wiele innych naszych ogólnych pytań. Z tego powodu zaznaczam to CW.

W kategorii „Świetny zarys dowodu” są to moje ulubione:

„ Niekierowana łączność w przestrzeni logów ” Omer Reingold.

„ Geometria, przepływy i algorytmy podziału grafów ” Sanjeev Arora, Satish Rao i Umesh Vazirani.

Fale Entropii, produkt zygzakowaty i nowe ekspandery o stałym stopniu przekazują wiele intuicji na temat produktów grafowych i ekspanderów, a pomysły są dostępne dla każdego, kto ma podstawową wiedzę na temat algebry liniowej.

Pamiętam, że naprawdę podoba mi się artykuł Lucy, który podaje spektralne przybliżenie do Maxa Cuta: http://arxiv.org/pdf/0806.1978v5.pdf .

Z wyjątkiem jasnego przedstawienia, ładnie maluje szerszy obraz: dlaczego jest jakieś przybliżenie MaxCut lepsze niż współczynnik-2, dlaczego można oczekiwać, że techniki spektralne mogłyby działać, jak jego algorytm odnosi się do nierówności Cheegera i do SDP Goemans-Williamson. Oprócz tego, że sam algorytm jest bardzo schludny.

Papier ekstrakcyjny Lucy Trevisana jest pięknie napisany - ówczesny pomysł był rewolucyjny, a prezentacja intuicji Lucy była świetna.

Nie jestem pewien, czy kwalifikuje się do TCS, ale klasyczny papier Kleinberga jest dobrym przykładem dobrego pisania. Przynajmniej tego używam jako przykładu, kiedy zadano mi to pytanie.

Autorytatywne źródła w środowisku hiperlinkowanym przez Jona M. Kleinberga http://www.cs.cornell.edu/home/kleinber/auth.pdf

Interesujące jest także porównanie tego artykułu z „artykułem Google” opublikowanym w WWW. Artykuł Kleinberga jest znacznie lepiej napisany.

Oded Goldreich's In a World of P = BPP jest jednym z najlepiej napisanych artykułów, jakie przeczytałem. Wynika to głównie z jasności ekspozycji, perspektywy pojęciowej i możliwości włączenia refleksji dotyczących znaczenia wyników w pracy.