Quels papiers tout le monde devrait-il lire?

Cette question est (inspirée par) / (honteusement volée à) une question similaire chez MathOverflow , mais je m'attends à ce que les réponses ici soient très différentes.

Nous avons tous des articles favoris dans nos domaines théoriques respectifs. De temps en temps, on trouve un article tellement stupéfiant (important, convaincant, trompeusement simple, etc.) qu'on veut le partager avec tout le monde. Alors listez ces papiers ici! Ils ne doivent pas nécessairement être issus de l'informatique théorique - tout ce qui, selon vous, pourrait plaire à la communauté est une bonne réponse.

Vous pouvez donner autant de réponses que vous voulez; s'il vous plaît mettez un papier par réponse ! Notez également qu'il s'agit d'un wiki de communauté, alors votez pour tout ce que vous aimez!

(Notez qu'il y avait une question précédente sur les articles dans la complexité de la théorie de la récursivité, mais elle est assez spécialisée.)

"Une théorie mathématique de la communication" de Claude Shannon, des classiques de la théorie de l'information. Très lisible.

( Miroir )

Le document de 1936 qui a probablement lancé l'informatique elle-même:

• Alan Turing, "On Numbers Computing, avec une application au problème d'Entscheidungs", Actes de la London Mathematical Society s2-42, 230-265, 1937. doi: 10.1112 / plms / s2-42.1.230

En seulement 36 pages, Turing formule (mais ne nomme pas) la machine de Turing, retransmet le fameux premier théorème d'incomplétude de Gödel en termes de calcul, décrit le concept d'universalité et montre en annexe que la calculabilité par les machines de Turing est équivalente à la calculabilité par Fonctions définissables par (comme l'ont étudié Church et Kleene).$\lambda$

" Réflexions sur la confiance " de Ken Thompson . Court, doux et hallucinant.

Ce que tout informaticien devrait savoir sur l'arithmétique en virgule flottante

Cet article explique et renforce la notion selon laquelle la virgule flottante n’est pas magique. Il explique les débordements, les débordements, ce que sont les nombres dénormalisés, ce que sont les NaN, ce que inf est et tout ce que cela implique. Après avoir lu cet article, vous saurez pourquoi a == a + 1.0 peut être vrai, pourquoi a == a peut être faux, pourquoi exécuter votre code sur deux machines différentes peut vous donner deux réponses différentes, pourquoi sommer des nombres de manière différente order peut vous donner une différence d’ordre de grandeur et toutes les choses loufoques qui se produisent dans le monde de la cartographie d’un nombre infini d’innombrables nombres sur un ensemble infiniment fini.

Une version modifiée est également disponible sur le Web.

Keshav est comment lire un papier . Vous pouvez également télécharger le document à partir d' ici .

Chemins, arbres et fleurs de J. Edmonds. Cet article sur le problème classique de l'optimisation combinatoire est non seulement bien écrit, mais indique également que la notion d '"algorithmes à temps polynomiaux" est essentiellement synonyme d'efficacité.

Réductibilité des problèmes combinatoires par Richard Karp. Le document contient ce que l'on appelle souvent les "problèmes d'origine de 21 NP-complets" de Karp. À bien des égards, cet article a véritablement motivé l’étude de l’exhaustivité des NP en démontrant son applicabilité à un domaine plus large. Très lisible.

Hartmanis et Stearns, "Sur la complexité de calcul des algorithmes" , Transactions de l'American Mathematical Society 117: 285-306 (1965).

Il s’agissait du premier article qui prenait l’étude de la complexité du temps au sérieux et constituait assurément la principale motivation du prix conjoint de Turing attribué à Hartmanis et Stearns. Bien que leurs définitions initiales ne correspondent pas exactement à celles que nous utilisons aujourd'hui, le document reste extrêmement lisible. Vous avez vraiment le sentiment de la situation dans l’ancienne frontière du "Far West" des années 60.

Ordinateurs mécaniques quantiques (PDF) de Richard Feynman.

Il introduit la notion de calcul quantique, décrit les circuits quantiques, explique comment les circuits classiques peuvent être simulés par des circuits quantiques et montre comment les circuits quantiques peuvent calculer des fonctions sans beaucoup de qubits de déchets (en utilisant un calcul).

Il montre ensuite comment tout circuit classique peut être encodé dans un hamiltonien indépendant du temps! Sa preuve est également valable pour les circuits quantiques, démontrant ainsi que les hamiltoniens évoluant dans le temps sont BQP-difficiles! Sa construction hamiltonienne est également utilisée dans la démonstration de la version quantique du théorème de Cook-Levin, prouvée par Kitaev, qui montre que l'hamiltonien k-local est une QMA-complète.

Les graphes d'expandage et leurs applications, S. Hoory, N. Linial et A. Wigderson est une très belle enquête sur les graphes d'expandage. Pas étonnant qu'il ait remporté le prix Conant 2008 de l'AMS.

Je tiens à rappeler que les graphiques d’extension sont l’ingrédient essentiel des avancées récentes dans le TCS, par exemple.

• algorithme d’espace de log pour la connectivité non dirigée (par Reingold, STOC, 2005)
• la preuve alternative du théorème PCP (par Dinur, ECCC, TR05-046, 2005)

et pas si récent:

• $O(\log n)$$O(n \log n)$$n$
• Codes de correction d'erreur codables et décodables à temps linéaire (par Spielman, STOC, 1995)

Des centaines de résultats d'impossibilité pour l'informatique distribuée par Fich et Ruppert. Une étude imagée lisible qui présente en réalité des centaines de résultats impossibles, y compris les questions fondamentales du domaine. Un morceau remarquable d'écriture explicative.

Je suis surpris de constater que personne n'a publié les "résultats optimaux d'inapproximabilité" de Hastad (JACM, 2001; à l'origine, STOC, 1997). Cet article de référence a été si bien écrit que vous ne pouvez y arriver qu'avec une maturité mathématique et vous donner envie de bien apprendre plusieurs choses, telles que ses techniques de Fourier, sa répétition parallèle, ses gadgets, etc.

$O((log N)^3)$$O\left(\exp\left(\left(\begin{matrix}\frac{64}{9}\end{matrix} b\right)^{1\over3} (\log b)^{2\over3}\right)\right)$

The Valiant's Theory of the Learnable (1984) a établi l'ordre du jour de la théorie de l'apprentissage pendant des décennies. C'est un document agréable et lisible!

Il existe également de nombreuses explications intuitives dans le document qui le rendent amusant et convaincant. Diverses parties de ce document sont toujours régulièrement citées dans les discussions entre COLT et ALT.

Peut-être trop basique, mais je suis choqué que personne n'ait mentionné les documents Lambda originaux de Steele et Sussman: SCHEME: Un interprète pour le calcul lambda étendu , Lambda: L'impératif ultime , Lambda: Le déclaratif ultime .

Les fonctions récursives des expressions symboliques de John McCarthy et leur calcul par machine, partie I.

Ceci est le document de base sur Lisp. Nous trouvons ici le premier évaluateur métacirculaire, s’adaptant sur une seule page. Son impact ne peut être surestimé, et il est toujours parfaitement lisible.

La complexité des procédures de démonstration de théorèmes par Stephen A. Cook. Cet article prouve que toutes les langues décidées par les machines de Turing non déterministes peuvent être (Cook) réduites à l’ensemble des tautologies propositionnelles.

L'importance de ce résultat est (au moins) double: premièrement, il montre qu'il existe des problèmes dans NP qui sont au moins aussi difficiles que toute la classe, les problèmes complets de NP ; de plus, il fournit un exemple concret d'un tel problème, qui peut ensuite être réduit à d'autres afin de prouver qu'il est complet.

De nos jours, les réductions de Karp sont plus couramment utilisées que les réductions de Cook, mais la preuve principale de ce document peut facilement être adaptée pour montrer que la SAT est NP- complète en ce qui concerne les réductions de Karp.

Call-by-value est dual à call-by-name par Philip Wadler est une bonne lecture.

CAR Hoare, une base axiomatique pour la programmation informatique .

Extrait du résumé: Cet article tente d'explorer les fondements logiques de la programmation informatique en utilisant des techniques qui ont d'abord été appliquées à l'étude de la géométrie et ont ensuite été étendues à d'autres branches des mathématiques.

Il a six pages qui sont assez faciles à suivre.

Alon, Matias et Szegedy, La complexité spatiale de l'approximation des moments de fréquence , JCSS 58 (1): 137-147, 1999.

Ce papier plutôt magique a été le premier à formaliser des algorithmes de transmission en continu et à établir des limites supérieures et inférieures rigoureuses pour les tâches fondamentales dans le modèle de diffusion en continu. Ses techniques sont simples, ses preuves sont belles et son impact a été profond. Le travail a valu au prix Gödel à Alon, Matias et Szegedy en 2005.

Le document d'Immerman prouvant le théorème connu à présent sous le nom de théorème d'Immerman – Szelepcsényi est un excellent exemple de document facile à lire, intelligent et court. J'adore l'histoire racontée dans l'intro.

N. Immerman, L'espace non déterministe est fermé sous complémentation, SIAM Journal on Computing 17, 1988, p. 935–938.

$f(n) \ge \log(n)$

$\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^2\right).$

$\text{NPSPACE} = \text{PSPACE}$$\text{P}$$\text{NP}$

Savitch, Walter J. (1970), "Relations entre complexités de bandes non déterministes et déterministes", Journal of Computer and System Sciences 4 (2): 177-192.

Russell Impagliazzo's Une vision personnelle de la complexité moyenne des cas . C’est un excellent document, car il est intelligemment écrit et résume l’état de la situation dans cinq «mondes» où nos conjectures sur la complexité sont résolues de diverses manières, donnant des conséquences concrètes dans chaque cas.

Algorithmes d'approximation améliorés pour des problèmes de coupure maximum et de satisfiabilité utilisant une programmation semi-finie de Goemans et Williamson.

Un bel exemple d’introduction d’une nouvelle technique pour obtenir des résultats bien meilleurs que ceux connus auparavant.

Extracteurs et générateurs pseudo-aléatoires de Luca Trevisan. Dans cet article, un bon extracteur d’aléatoire est construit à l’aide de codes de correction d’erreurs et de conceptions combinatoires. La construction est assez facile à comprendre, mais elle est complètement renversante, car il n’est pas évident de savoir quel est le lien entre les extracteurs, les codes et les dessins.

Après tout, c’est un bon exemple de résultat dans TCS qui nécessite une combinatoire sophistiquée.

Comment rédiger une preuve , par Leslie Lamport.

L'influence des variables sur les fonctions booléennes, J. Kahn, G. Kalai et N. Linial

Ce document présente les techniques de Fourier pour la communauté TCS et résout un problème ouvert très soigné.

Je trouve ce papier très lisible.

Si je peux citer Sarah Palin à ce sujet: "Tous".

Plus sérieusement, je pense que la plupart des papiers ne doivent pas être lus dans l'original. À mesure que le temps passe, les gens trouvent un meilleur moyen de comprendre et de présenter le problème / la solution d'origine. À l'exception du document original de Turing, qui revêt une importance historique, je ne recommanderais pas de lire la plupart des documents originaux s'il y a un travail de suivi qui l'a nettoyé. En particulier, beaucoup de choses sont présentées beaucoup mieux dans les livres que dans l'original.

• N. Chomsky. Trois modèles pour la description du langage. Transactions IEEE sur la théorie de l'information 3. 1956. doi: 10.1109 / TIT.1956.1056813

Chomsky analyse comment les modèles mathématiques peuvent être utilisés pour décrire le langage naturel, d'un point de vue linguistique.

Les propositions formellement indécidables de Kurt Gödel de Principia Mathematica et des systèmes associés .