Beiträge, die jeder Komplexitätstheoretiker lesen sollte

14

Ich beginne meine Doktorarbeit in diesem Herbst und plane, mich für meine Diplomarbeit mit Komplexitätstheorie zu befassen.

Ich erstelle eine Liste wichtiger Artikel, die jeder Komplexitätstheoretiker kennen sollte.

Welche Papiere würden Sie einer Person wie mir vorschlagen? Und erläutern Sie kurz, warum Sie das Papier für wichtig halten.

cc.complexity-theory reference-request big-list neuer Student
quelle
8
Haben Sie bereits überprüft, welche Papiere jeder lesen sollte?
Juho,
3
Ja. Warum ist dies nicht nur ein Duplikat dieser Frage?
Suresh Venkat
2
Das OP hat diese Frage wahrscheinlich einfach nicht bemerkt.
Huck Bennett
3
Ich denke nicht, dass dies ein Duplikat der anderen Frage ist. Die andere Frage ist, welche Artikel jeder lesen sollte (dh von Interesse für alle theoretischen Informatiker). Dieser scheint ein Doktorand zu sein, der sich mit Komplexitätstheorie befasst und nach wichtigen Artikeln in der Komplexitätstheorie sucht. Solche Arbeiten sind für theoretische Informatiker, die sich nicht mit Komplexitätstheorie auskennen, möglicherweise nicht von Interesse. Die Antworten werden unterschiedlich sein, damit sie IMO nicht duplizieren.
Kaveh
2
@Kaveh: Ich denke, diese Frage wird vom anderen subsumiert. Viele der Antworten beziehen sich auf Komplexitätspapiere.
Huck Bennett

Antworten:

10

Ryan Williams uneinheitliche ACC Circuit Lower Bounds und alle darin genannten Ergebnisse.

Dies ist nicht nur ein aktuelles wichtiges Ergebnis, sondern auch ein sehr gut geschriebenes Papier. Darüber hinaus decken die Ergebnisse, die das Papier verwendet und zitiert, einen ziemlich guten Bereich von Ergebnissen der grundlegenden Komplexität ab. Wenn Sie also die Referenzen durchgehen und diese auch lesen - bis zu einem Punkt, an dem Sie jeden Teil der ACC-Untergrenze anhand der ersten Prinzipien verstehen -, wäre dies ein ausgezeichneter Anfang für eine Ausbildung in Komplexität mit Abschluss.

Joshua Grochow
quelle
3
die casual tour ist auch sehr zu empfehlen: arxiv.org/abs/1111.1261
Sasho Nikolov
9

Obwohl dies keine direkte Antwort auf Ihre Frage ist, möchte ich das folgende Buch empfehlen:

Juwelen der theoretischen Informatik von Uwe Schöning und Randall J. Pruim.

Die meisten seiner Kapitel beziehen sich auf die Komplexitätstheorie. Das Buch kann als eine schöne Sammlung der Ergebnisse einiger wichtiger Forschungsarbeiten angesehen werden. Sie können die Papiere von den Resultaten erhalten!

Abuzer Yakaryilmaz
quelle
7

Ich würde die Ergebnisse in empfehlen

Der Complexity Theory Companion von Hemaspaandra und Ogihara.

Es ist eher nach Techniken als nach Ergebnissen organisiert, obwohl die Technik oft für ein bestimmtes Ergebnis entwickelt wurde und mehrere grundlegende Ergebnisse und wichtige Beweistechniken abdeckt.

Joshua Grochow
quelle
6

1) R. Lader, N. Lynch und A. Selman. Ein Vergleich der Polynomzeitreduzierbarkeiten. Theoretical Computer Science, 1 (2): 103-124, 1975.

2) LG Valiant "Die Komplexität der Berechnung der permanenten", Theoretical Computer Science, 8 (1979), S. 181-201.

3) A. Blass & Y. Gurevich "Über das einzigartige Erfüllbarkeitsproblem". Information and Control, 55 (1-3) Seiten 80-88, 1982.

4) J. Balcazar, R. Book & U. Schoning. "The Polynomial-Time Hierarchy & Sparse Oracles" Journal des Associate for Computing Machinery, Band 33, Nr. 3. July1986. Seiten 603-617.

5) LG Valiant & V. Vazirani "NP ist so einfach wie das Erkennen einzigartiger Lösungen" Theoretical Computer Science 47 (1986), Seiten 85-93.

6) E. Allender. Die Komplexität von spärlichen Mengen in P. In Verfahren der 1. Struktur in der Komplexitätstheorie Konferenz, Seiten 1-11. Springer-Verlag Lecture Notes in Computer Science # 223, Juni 1986.

6) R. Beigel. Über die relativierte Kraft zusätzlicher Akzeptanzpfade. In Tagungsband der 4th Structure in Complexity Theory Conference, Seiten 216-224. IEEE Computer Society Press, Juni 1989.

7) R.Beigel & J. Gill "Zählen von Klassen: Schwellenwerte, Parität, Modifikationen und Wenigkeit" Theoretische Informatik Band 103 Seiten 3-23. 1992.

8) S. Fenner, L. Fortnow & S. Kurtz "Gap-Definable Counting Classes", Fachzeitschrift für Computer- und Systemwissenschaften, Band 48, Seiten 116-148, 1994.

9) R. Beigel, H. Buhrman und L. Fortnow. NP ist möglicherweise nicht so einfach wie das Auffinden einzigartiger Lösungen. In Proceedings of the 30th ACM Symposium on Theory of Computing, S. 203-208. ACM Press, Mai 1998.

10) B. Borchert, L. Hemaspaandra & J. Rothe "Restriktive Akzeptanz reicht für Äquivalenzprobleme" LMS J Comput. Mathe 3 Seiten 86-95 2000.

Tayfun Pay
quelle
5

Ich stimme der obigen Antwort von Abuzer zu: Ich denke, dass jedes Kapitel eines Buches über Computerkomplexität (wie Aroras und Baracks " Computational Complexity: a Modern Approach " oder Goldreichs " Computational Complexity: a Conceptual Perspective ") klarere Informationen enthält (und häufig klarer erklärt) Weise) Ergebnisse, die aus wichtigen / grundlegenden Papieren stammen. Und während Sie ein Buch über Computerkomplexität lesen, können Sie besser verstehen, warum sie als wichtig angesehen werden.

Dies sind jedoch meine Favoriten:

Marzio De Biasi
quelle