Papiers que tout théoricien de la complexité devrait lire

14

Je commence mon doctorat cet automne et je prévois de travailler en théorie de la complexité pour ma thèse.

Je compile une liste d'articles importants que tout théoricien de la complexité devrait connaître.

Quels papiers suggéreriez-vous à une personne comme moi? Et veuillez expliquer brièvement pourquoi vous pensez que le document est important.

cc.complexity-theory reference-request big-list nouvel étudiant diplômé
la source
8
Avez-vous déjà vérifié quels articles chacun devrait-il lire?
Juho
3
Oui. Pourquoi n'est-ce pas simplement un double de cette question.
Suresh Venkat
2
Le PO n'a probablement pas remarqué cette question.
Huck Bennett
3
Je ne pense pas que ce soit un double de l'autre question. L'autre question consiste à demander des articles que tout le monde devrait lire (c'est-à-dire qui intéressent tous les informaticiens théoriques), celui-ci semble être un étudiant diplômé commençant des recherches en théorie de la complexité qui recherche des articles importants en théorie de la complexité. Ces articles pourraient ne pas intéresser les informaticiens théoriciens qui ne sont pas des experts en théorie de la complexité. Les réponses vont être différentes, donc elles ne sont pas des doubles de l'OMI.
Kaveh
2
@Kaveh: Je pense que cette question est subsumée par l'autre. Beaucoup de réponses concernent des articles complexes.
Huck Bennett

Réponses:

10

Limites inférieures du circuit ACC non uniforme de Ryan William et tous les résultats qui y sont cités.

Non seulement c'est un résultat important récent, mais c'est un article très bien écrit. De plus, les résultats que le papier utilise et cite couvrent une assez bonne gamme de résultats de complexité séminale. Donc, si vous retracez les références et les lisez également - arrivez à un point où vous comprenez chaque partie de l'ACC à partir des premiers principes - je pense que ce serait un excellent début pour une éducation de complexité supérieure.

Joshua Grochow
la source
3
la visite décontractée est également fortement recommandée: arxiv.org/abs/1111.1261
Sasho Nikolov
9

Bien que ce ne soit pas une réponse directe à votre question, je voudrais recommander le livre suivant:

Gemmes de l'informatique théorique par Uwe Schöning et Randall J. Pruim.

La plupart de ses chapitres sont liés à la théorie de la complexité. Le livre peut être considéré comme une belle collection des résultats de certains documents de recherche importants. Vous pouvez obtenir les articles des résultats!

Abuzer Yakaryilmaz
la source
7

Je recommanderais les résultats dans

The Complexity Theory Companion par Hemaspaandra et Ogihara.

Il est organisé autour de techniques plutôt que de résultats, bien que souvent la technique ait été développée pour un résultat particulier, et elle couvre plusieurs résultats séminaux et techniques de preuve importantes.

Joshua Grochow
la source
6

1) R. Lader, N. Lynch et A. Selman. Une comparaison des réductibilités de temps polynomiales. Informatique théorique, 1 (2): 103-124, 1975.

2) LG Valiant «La complexité du calcul du permanent», Informatique théorique, 8 (1979), p. 181-201.

3) A. Blass & Y. Gurevich «Sur le problème de satisfiabilité unique». Information et contrôle, 55 (1-3) pages 80-88, 1982.

4) J. Balcazar, R. Book & U. Schoning. «La hiérarchie polynomiale-temps et les oracles clairsemés» Journal de l'Associate for Computing Machinery, Vol 33, No3. Juillet1986. pages 603-617.

5) LG Valiant & V. Vazirani «NP est aussi simple que de détecter des solutions uniques» Théorie informatique 47 (1986) pages 85-93.

6) E. Allender. La complexité des ensembles clairsemés en P. Dans les actes de la 1ère Conférence Structure in Complexity Theory, pages 1-11. Notes de conférence Springer-Verlag en informatique # 223, juin 1986.

6) R. Beigel. Sur la puissance relativisée de chemins d'acceptation supplémentaires. Dans les actes de la 4e conférence Structure in Complexity Theory, pages 216-224. IEEE Computer Society Press, juin 1989.

7) R.Beigel & J. Gill «Classes de comptage: seuils, parité, mods et peu de poids» Théorie informatique théorique Volume 103 Pages 3-23. 1992.

8) S. Fenner, L. Fortnow et S. Kurtz «Gap-Definable Counting Classes» Journal of Computer And System Sciences Volume 48 Pages 116-148 1994.

9) R. Beigel, H. Buhrman et L. Fortnow. NP pourrait ne pas être aussi simple que de détecter des solutions uniques. Dans les Actes du 30ème Symposium ACM sur la Théorie de l'Informatique, pages 203-208. ACM Press, mai 1998.

10) B. Borchert, L. Hemaspaandra et J. Rothe «Suffices d'acceptation restrictive pour les problèmes d'équivalence» LMS J Comput. Math 3 Pages 86-95 2000.

Tayfun Pay
la source
5

Je suis d'accord avec la réponse d'Abuzer ci-dessus: je pense que chaque chapitre d'un livre sur la complexité computationnelle (comme Arora et Barack " Computational Complexity: a Modern Approach " ou Goldreich " Computational Complexity: a Conceptual Perspective ") contient (et explique souvent de manière plus claire) manière) des résultats qui proviennent de documents importants / fondamentaux. Et en lisant un livre sur la complexité informatique, vous pouvez mieux comprendre pourquoi ils sont considérés comme importants.

Cependant ce sont mes favoris:

Marzio De Biasi
la source