14
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • 8
    $\begingroup$ Did you already check What papers should everyone read? $\endgroup$
    – Juho
    Commented Jul 9, 2012 at 21:30
  • 3
    $\begingroup$ Yes. Why is this not just a duplicate of that question. $\endgroup$
    – Suresh Venkat
    Commented Jul 10, 2012 at 0:01
  • 2
    $\begingroup$ The OP probably just didn't notice that question. $\endgroup$
    – Huck Bennett
    Commented Jul 10, 2012 at 0:08
  • 3
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Jul 10, 2012 at 1:37
  • 2
    $\begingroup$ @Kaveh: I think this question is subsumed by the other. Many of the answers their are about complexity papers. $\endgroup$
    – Huck Bennett
    Commented Jul 10, 2012 at 4:29

5 Answers 5

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
1
9
$\begingroup$

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!

Improve this answer
$\endgroup$
7
$\begingroup$

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.

Improve this answer
$\endgroup$
0
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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:

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.