Bons exemples pour bien écrire en TCS

Je révisais un manuscrit d'étudiant. L'élève a fait remarquer qu'il serait bien de voir des exemples d'écriture de qualité dans les publications, et je me suis rendu compte que je ne pouvais pas vraiment trouver de bons exemples par cœur.

Quels sont les meilleurs exemples d'écriture mathématique de qualité que vous ayez vus?

Règles:

• Je préférerais les papiers TCS autant que possible. Notre style est suffisamment différent des travaux mathématiques classiques pour que je pense qu'il vaut mieux se concentrer sur le SDC (pourquoi aussi je demande ici et non sur MO)
• cela aiderait si vous indiquiez ce que vous pensiez exactement que le document avait bien fonctionné. Toute exposition n’est pas bonne en tout. Certains papiers ont de très bonnes résumés, certains utilisent la notation de manière très efficace et d’autres transmettent l’intuition de façon magistrale.
• si possible, s'il vous plaît lien vers le papier.

J'espère que cela deviendra une ressource, comme beaucoup de nos autres grandes questions. Je le marque CW pour cette raison.

Dans la catégorie "Grand aperçu des épreuves", voici mes favoris:

" Connectivité non dirigée dans l'espace journal " par Omer Reingold.

" Algorithmes de géométrie, de flux et de partitionnement de graphes " de Sanjeev Arora, Satish Rao et Umesh Vazirani.

Les ondes d'entropie, le produit graphique en zig-zag et les nouveaux expandeurs à degré constant transmettent beaucoup d'intuition sur les produits graphiques et les graphiques expandeurs. Les idées sont accessibles à quiconque ayant des connaissances de base en algèbre linéaire.

Je me souviens vraiment avoir aimé le papier de Luca donnant une approximation spectrale à Max Cut: http://arxiv.org/pdf/0806.1978v5.pdf .

Hormis l'exposé clair, il brosse un tableau plus général: pourquoi est-il difficile de faire une approximation meilleure que le facteur de 2 de MaxCut, pourquoi on s'attendrait à ce que les techniques spectrales fonctionnent, que son algorithme se rapporte le SDP Goemans-Williamson. En plus de l'algorithme lui-même étant très soigné.

Le papier d'extraction de Luca Trevisan est magnifiquement écrit - l'idée était alors révolutionnaire et l'exposition de Luca sur l'intuition était formidable.

Je ne suis pas sûr qu'il soit qualifié pour le SDC, mais le papier classique de Kleinberg est un bon exemple pour bien écrire. Au moins c'est ce que j'utilise comme exemple quand on me pose cette question.

Sources faisant autorité dans un environnement hyper-lié par Jon M. Kleinberg http://www.cs.cornell.edu/home/kleinber/auth.pdf

Il est également très intéressant de mettre en contraste ce document avec le "Google paper" publié sur le Web. Le papier de Kleinberg est beaucoup mieux écrit.

Oded Goldreich's Dans un monde de P = BPP est l'un des meilleurs articles écrits que j'ai lu. Cela est principalement dû à la clarté de l'exposé, à la perspective conceptuelle et au choix d'inclure des réflexions sur la signification des résultats dans l'article.