Papers every complexity theorist should read

Question

I am starting my PhD this autumn and I am planning to work in complexity theory for my thesis.

I am compiling a list of important papers that every complexity theorist should know.

What papers would you suggest to a person like me? And please briefly explain why you think the paper is important.

I don't think this is a duplicate of the other question. The other question is asking for papers everyone should read (i.e. of interest to all theoretical computer scientists), this one seems to be a grad student starting research in complexity theory who is looking for important papers in complexity theory. Such papers might not be of interest to theoretical computer scientists who are not experts in complexity theory. The answers are going to be different so they are not duplicate IMO. — Kaveh, Jul 10 '12 at 01:37
@Kaveh The question should be changed to community-wiki and the title adjusted if it is grad-student specific. — Artem Kaznatcheev, Jul 10 '12 at 02:19
@Kaveh: I think this question is subsumed by the other. Many of the answers their are about complexity papers. — Huck Bennett, Jul 10 '12 at 04:29
@Huck, I don't think it is subsumed by the other question as I explained above. There is an intersection but it doesn't seem to me that one is a subset of the other. — Kaveh, Jul 10 '12 at 07:44
@Huck: I don't think it's subsumed by the other question because this question really seems to be about papers that every complexity theorist should read and know at the beginning of their career. The other list is a good list, but I think the answers to this question that are already here demonstrate how it's different. — Joshua Grochow, Jul 12 '12 at 23:00
see also mathoverflow, What are the most important results (and papers) in complexity theory that every one should know? — vzn, Sep 20 '12 at 05:20

score 10 · Answer 1 · answered Jul 10 '12 at 19:01

Ryan William's Non-uniform ACC Circuit Lower Bounds and all the results cited therein.

Not only is this a recent important result, it is a very well-written paper. Furthermore, the results the paper uses and cites cover a pretty good range of seminal complexity results. So if you trace through the references and read those as well - get to a point where you understand every part of the ACC lower bound from first principles - I would think that would be an excellent start to a graduate complexity education.

the casual tour is also highly recommended: http://arxiv.org/abs/1111.1261 — Sasho Nikolov, Jul 15 '12 at 15:59

score 9 · Answer 2 · answered Jul 10 '12 at 09:32

Although this is not a direct answer to your question, I would like to recommend the following book:

Gems of Theoretical Computer Science by Uwe Schöning and Randall J. Pruim.

Most of its chapters are related to complexity theory. The book can be seen as a nice collection of the results from some important research papers. You can get the papers from the results!

score 7 · Answer 3 · answered Jul 10 '12 at 18:55

I'd recommend the results in

The Complexity Theory Companion by Hemaspaandra and Ogihara.

It's organized around techniques rather than results, though often the technique was developed for a particular result, and it covers several seminal results and important proof techniques.

score 6 · Answer 4 · answered Jul 10 '12 at 15:26

1)R. Lader, N. Lynch, and A. Selman. A comparison of polynomial time reducibilities. Theoretical Computer Science, 1(2):103-124, 1975.

2)L.G. Valiant “The complexity of computing the permanent”, Theoretical Computer Science, 8 (1979), pp. 181-201.

3)A. Blass & Y. Gurevich “On the unique satisfiability problem.” Information and Control, 55(1-3) pages 80-88, 1982.

4)J. Balcazar, R. Book & U. Schoning. “The Polynomial-Time Hierarchy & Sparse Oracles” Journal of the Associate for Computing Machinery, Vol 33, No3. July1986. pages 603-617.

5)L.G. Valiant & V. Vazirani “NP is as easy as detecting Unique Solutions” Theoretical Computer Science 47 (1986) pages 85-93.

6)E. Allender. The complexity of sparse sets in P. In proceedings of the 1st Structure in Complexity Theory Conference, pages 1-11. Springer-Verlag Lecture Notes in Computer Science #223, June 1986.

6)R. Beigel. On the relativized power of additional accepting paths. In proceedings of the 4th Structure in Complexity Theory Conference, pages 216-224. IEEE Computer Society Press, June 1989.

7)R.Beigel & J. Gill “Counting Classes: Thresholds, parity, Mods, and Fewness” Theoretical Computer Science Volume 103 Pages 3-23. 1992.

8)S. Fenner, L. Fortnow & S. Kurtz “Gap-Definable Counting Classes” Journale of Computer And System Sciences Volume 48 Pages 116-148 1994.

9)R. Beigel, H. Buhrman, and L. Fortnow. NP might not be as easy as detecting unique solutions. In Proceedings of the 30th ACM Symposium on Theory of Computing, pages 203-208. ACM Press, May 1998.

10)B. Borchert, L. Hemaspaandra & J. Rothe “Restrictive Acceptance Suffices for Equivalance Problems” LMS J Comput. Math 3 Pages 86-95 2000.

score 5 · Answer 5 · answered Jul 10 '12 at 14:57

I agree with Abuzer's answer above: I think that every chapter of a computational complexity book (like Arora and Barack's "Computational Complexity: a Modern Approach" or Goldreich's "Computational Complexity: a Conceptual Perspective" ) contains (and often explains in a more clear way) results that come from important/fundamental papers. And while reading a computational complexity book you can better understand why they are considered important.

However these are my favourites:

Savitch's theorem: Savitch, Walter J. (1970), "Relationships between nondeterministic and deterministic tape complexities", Journal of Computer and System Sciences 4 (2): 177–192, DOI:10.1016/S0022-0000(70)80006-X
Cook-Levin theorem: Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158
J. Hopcroft, W. Paul, and L. Valiant, On time versus space, J. ACM, 24, 332–337 (1977)
T. P. Baker, J. Gill, R. Solovay. Relativizations of the P =? NP Question. SIAM Journal on Computing, 4(4): 431-442 (1975)

Papers every complexity theorist should read

5 Answers5