Welche Papiere sollten alle lesen?

Diese Frage ist (inspiriert von) / (schändlicherweise gestohlen von) einer ähnlichen Frage bei MathOverflow , aber ich gehe davon aus , dass die Antworten hier ganz anders ausfallen werden.

Wir alle haben Lieblingsarbeiten in unseren jeweiligen theoretischen Bereichen. Hin und wieder findet man eine Zeitung, die so erstaunlich ist (z. B. wichtig, zwingend, täuschend einfach usw.), dass man sie mit allen teilen möchte. Schreiben Sie also diese Papiere hier auf! Sie haben nicht haben , um aus der theoretischen Informatik sein - alles , was Sie denken , an die Gemeinde ansprechen könnte eine gute Antwort.

Sie können so viele Antworten geben, wie Sie möchten. Bitte legen Sie ein Papier pro Antwort ! Beachten Sie auch, dass dies Community-Wiki ist. Stimmen Sie also über alles ab, was Ihnen gefällt!

(Beachten Sie, dass es bereits eine Frage zu rekursionstheoretisch komplexen Arbeiten gegeben hat , die jedoch sehr spezialisiert ist.)

"Eine mathematische Theorie der Kommunikation" von Claude Shannon, Klassiker der Informationstheorie. Sehr gut lesbar.

( Spiegel )

Das Papier von 1936, mit dem die Informatik wohl begonnen hat:

• Alan Turing, "Über berechenbare Zahlen mit einer Anwendung auf das Entscheidungsproblem", Proceedings of the London Mathematical Society s2-42, 230–265, 1937. doi: 10.1112 / plms / s2-42.1.230

Auf nur 36 Seiten formuliert Turing die Turing-Maschine (benennt sie aber nicht), greift Gödels berühmten ersten Unvollständigkeitssatz in Bezug auf die Berechnung auf, beschreibt das Konzept der Universalität und zeigt im Anhang, dass die Berechenbarkeit durch Turing-Maschinen der Berechenbarkeit durch Funktionen (wie von Church und Kleene untersucht).$\lambda$

Ken Thompsons " Reflections on Trusting Trust ". Kurz, süß und umwerfend.

Was jeder Informatiker über Gleitkomma-Arithmetik wissen sollte

Dieser Artikel erklärt und bekräftigt den Gedanken, dass Fließkommazahlen keine Magie sind. Es erklärt Überlauf, Unterlauf, was denormalisierte Zahlen sind, was NaNs sind, was inf ist und all die Dinge, die diese implizieren. Nachdem Sie diesen Artikel gelesen haben, werden Sie wissen, warum a == a + 1.0 wahr sein kann, warum a == a falsch sein kann, warum das Ausführen Ihres Codes auf zwei verschiedenen Computern Ihnen zwei verschiedene Antworten geben kann, warum das Summieren von Zahlen in einer anderen order kann Ihnen eine Größenordnungsdifferenz geben und all das verrückte Zeug, das in der Welt der Abbildung einer unzählig unendlichen Menge von Zahlen auf eine zählbar endliche Menge passiert.

Eine bearbeitete Version ist auch im Internet verfügbar.

Keshavs Wie man eine Zeitung liest . Sie können auch das Papier von Download hier .

Pfade, Bäume und Blumen von J. Edmonds. Dieses Papier über das klassische Problem der kombinatorischen Optimierung ist nicht nur gut geschrieben, sondern stellt auch fest, dass der Begriff "Polynom-Zeit-Algorithmen" im Wesentlichen ein Synonym für Effizienz ist.

Reduzierbarkeit bei kombinatorischen Problemen von Richard Karp. Das Papier enthält das, was oft als Karps "ursprüngliche 21 NP-vollständige Probleme" bezeichnet wird. In vielerlei Hinsicht hat dieses Papier die Untersuchung der NP-Vollständigkeit wirklich motiviert, indem es die Anwendbarkeit auf ein breiteres Gebiet demonstrierte. Sehr gut lesbar.

Hartmanis und Stearns, "Über die rechnerische Komplexität von Algorithmen" , Transactions of the American Mathematical Society 117: 285–306 (1965)

Dies war die erste Veröffentlichung, die sich ernsthaft mit der Zeitkomplexität befasste, und sicherlich der Hauptantrieb für den gemeinsamen Turing-Preis von Hartmanis und Stearns. Während ihre anfänglichen Definitionen nicht ganz das sind, was wir heute verwenden, bleibt das Papier äußerst lesbar. Man bekommt wirklich das Gefühl, wie die Dinge in der alten "Wild West" -Grenze der 60er Jahre waren.

Quantenmechanische Computer (PDF) von Richard Feynman.

Er führt in die Idee der Quantenberechnung ein, beschreibt Quantenschaltungen, erklärt, wie klassische Schaltungen durch Quantenschaltungen simuliert werden können, und zeigt, wie Quantenschaltungen Funktionen ohne viele Müll-Qubits berechnen können (ohne Berechnung).

Er zeigt dann, wie jede klassische Schaltung in einen zeitunabhängigen Hamiltonianer kodiert werden kann! Sein Beweis gilt auch für Quantenschaltungen, was zeigt, dass die Zeit, in der sich Hamiltonianer entwickeln, BQP-schwer ist! Seine Hamiltonsche Konstruktion wird auch im Beweis der von Kitaev bewiesenen Quantenversion des Cook-Levin-Theorems verwendet, die zeigt, dass k-lokaler Hamiltonscher QMA-vollständig ist.

Expandergraphen und ihre Anwendungen, S. Hoory, N. Linial und A. Wigderson, sind eine sehr schöne Übersicht über Expandergraphen. Kein Wunder, dass es 2008 den AMS Conant Prize gewann.

Ich möchte daran erinnern, dass Expander-Graphen der Hauptbestandteil der jüngsten Durchbrüche in TCS sind, z.

• Log-Space-Algorithmus für ungerichtete Konnektivität (von Reingold, STOC, 2005)
• der alternative Beweis des PCP-Theorems (von Dinur, ECCC, TR05-046, 2005)

und nicht so aktuell:

• $O(\log n)$$O(n \log n)$$n$
• Linear zeitcodierbare und decodierbare Fehlerkorrekturcodes (von Spielman, STOC, 1995)

Hunderte von Unmöglichkeitsergebnissen für Distributed Computing von Fich und Ruppert. Eine lesbare, bildliche Übersicht, die tatsächlich Hunderte von Unmöglichkeitsergebnissen enthält, einschließlich der Kernfragen des Fachgebiets. Ein bemerkenswertes Stück Expository-Schreiben.

Ich bin überrascht, dass niemand Hastads "Some Optimal Inapproximability Results" (JACM 2001; ursprünglich STOC 1997) gefunden hat. Dieses wegweisende Papier wurde so gut geschrieben, dass Sie es nur mit mathematischer Reife erreichen können. Es wird Sie dazu bringen, einige Dinge gut zu lernen, wie Fouriertechniken, parallele Wiederholungen, Gadgets und so weiter.

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

Les Valiants Theory of the Learnable (1984) war jahrzehntelang das Leitmotiv der Lerntheorie und es ist eine schöne und lesbare Arbeit!

Das Papier enthält auch eine Reihe intuitiver Erklärungen, die Spaß machen und überzeugen. In COLT / ALT-Gesprächen werden noch immer verschiedene Teile dieses Papiers routinemäßig zitiert.

Vielleicht zu einfach , aber ich bin schockiert, dass niemand die originalen Lambda-Papiere von Steele und Sussman erwähnt hat: SCHEMA: Ein Interpreter für erweiterte Lambda-Rechnung , Lambda: Der ultimative Imperativ , Lambda: Der ultimative Deklarativ .

John McCarthys rekursive Funktionen symbolischer Ausdrücke und ihre maschinelle Berechnung, Teil I.

Dies ist das Grundpapier zu Lisp. Hier finden wir den ersten Metacircular Evaluator, der auf eine einzelne Seite passt. Ihre Wirkung kann nicht überbewertet werden und sie ist immer noch hervorragend lesbar.

Die Komplexität der Theorembeweisungsverfahren von Stephen A. Cook. Dieser Aufsatz beweist, dass alle Sprachen, die von polytime nichtdeterministischen Turing-Maschinen entschieden werden, auf die Menge der Satz-Tautologien (koch-) reduziert werden können.

Die Wichtigkeit dieses Ergebnisses ist (mindestens) zweifach: Erstens zeigt es, dass es in NP Probleme gibt, die mindestens so schwer sind wie die ganze Klasse, die NP- vollständigen Probleme; Darüber hinaus liefert es ein konkretes Beispiel für ein solches Problem, das dann auf andere reduziert werden kann, um zu beweisen, dass sie vollständig sind.

Heutzutage werden Karp-Reduktionen häufiger verwendet als Cook-Reduktionen, aber der Hauptbeweis dieses Papiers kann leicht angepasst werden, um zu zeigen, dass SAT in Bezug auf Karp-Reduktionen NP- vollständig ist.

Call-by-Value ist gleichbedeutend mit Call-by-Name, da Philip Wadler eine gute Lektüre ist.

CAR Hoare, eine axiomatische Basis für die Computerprogrammierung .

Aus dem Abstrakten: In dieser Arbeit wird versucht, die logischen Grundlagen der Computerprogrammierung mit Techniken zu erforschen, die zuerst in der Erforschung der Geometrie angewendet und später auf andere Bereiche der Mathematik ausgeweitet wurden.

Es hat sechs Seiten, die recht einfach zu befolgen sind.

Alon, Matias und Szegedy, Die räumliche Komplexität der Approximation der Frequenzmomente , JCSS 58 (1): 137-147, 1999.

Dieses eher magische Papier war das erste, das Streaming-Algorithmen formalisierte und strenge Ober- und Untergrenzen für grundlegende Aufgaben im Streaming-Modell nachwies. Seine Techniken sind einfach, seine Beweise sind wunderschön und seine Wirkung war tiefgreifend. Für diese Arbeit wurden Alon, Matias und Szegedy 2005 mit dem Gödel-Preis ausgezeichnet.

Immermans Aufsatz, der den Satz von Immerman-Szelepcsényi beweist, ist ein gutes Beispiel für einfach zu lesende, kluge und kurze Aufsätze. Ich liebe die Geschichte im Intro.

N. Immerman, Der nichtdeterministische Raum wird unter Komplementierung geschlossen, SIAM Journal on Computing 17, 1988, S. 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), "Beziehungen zwischen nicht deterministischen und deterministischen Bandkomplexitäten", Journal of Computer and System Sciences 4 (2): 177–192.

Russell Impagliazzos persönliche Sicht auf die Komplexität von Durchschnittsfällen . Dies ist ein großartiges Papier, weil es geschickt geschrieben ist und den Sachverhalt in fünf "Welten" zusammenfasst, in denen unsere Vermutungen über die Komplexität auf verschiedene Weise gelöst werden und jeweils reale Konsequenzen haben.

Verbesserte Approximationsalgorithmen für Probleme mit maximalem Schnitt und Erfüllbarkeit durch semidefinite Programmierung von Goemans und Williamson.

Ein gutes Beispiel für die Einführung einer neuen Technik, um Ergebnisse zu erzielen, die viel besser sind als die zuvor bekannten.

Extraktoren und Pseudozufallsgeneratoren von Luca Trevisan. In diesem Artikel wird ein guter Zufallsextraktor mit Hilfe von Fehlerkorrekturcodes und kombinatorischen Entwürfen erstellt. Die Konstruktion ist recht einfach zu verstehen, aber sie ist absolut umwerfend, da die Verbindung zwischen Extraktoren, Codes und Designs überhaupt nicht ersichtlich ist.

Immerhin ist es ein gutes Beispiel für ein Ergebnis in TCS, das einige ausgefallene Kombinatorik erfordert.

Wie man einen Beweis schreibt , von Leslie Lamport.

Der Einfluss von Variablen auf boolesche Funktionen, J. Kahn, G. Kalai und N. Linial

In diesem Artikel wurden Fouriertechniken für die TCS-Community vorgestellt und ein sehr einfaches offenes Problem gelöst.

Ich finde dieses Papier sehr lesbar.

Wenn ich Sarah Palin zu diesem Thema zitieren darf: "Alle von ihnen".

Im Ernst, ich denke, die meisten Artikel sollten nicht im Original gelesen werden. Mit der Zeit finden die Menschen heraus, wie sie das ursprüngliche Problem / die ursprüngliche Lösung besser verstehen und darstellen können. Mit Ausnahme des Turing-Originalpapiers, das von historischer Bedeutung ist, würde ich nicht empfehlen, die meisten Originalpapiere zu lesen, wenn es Nacharbeiten gibt, die es bereinigen. Vor allem vieles wird in Büchern viel besser dargestellt als im Original.

• N. Chomsky. Drei Modelle zur Beschreibung der Sprache. IEEE-Transaktionen zur Informationstheorie 3. 1956. doi: 10.1109 / TIT.1956.1056813

Chomsky analysiert, wie mathematische Modelle verwendet werden können, um natürliche Sprache aus sprachlicher Sicht zu beschreiben.

Kurt Gödels Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme .