<p>Ryan William's <a href="https://www.stanford.edu/~rrwill/acc-lbs.pdf">Non-uniform ACC Circuit Lower Bounds</a> and all the results cited therein. </p>

<p>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.</p>

CC BY-SA 3.0
2012-07-15T15:59:40.797Z
the casual tour is also highly recommended: http://arxiv.org/abs/1111.1261
Sasho Nikolov
CC BY-SA 3.0
2012-07-10T19:01:00.017Z
2012-07-10T19:01:00.017Z
Joshua Grochow
<p>Although this is not a direct answer to your question, I would like to recommend the following book:</p>

<blockquote>
  <p><strong><a href="http://www.calvin.edu/~rpruim/publications/gems/">Gems of Theoretical Computer Science</a></strong> by Uwe Schöning and Randall J. Pruim.</p>
</blockquote>

<p>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!</p>

CC BY-SA 3.0
2012-07-10T09:32:02.603Z
2012-07-10T09:32:02.603Z
Abuzer Yakaryilmaz
<p>I'd recommend the results in </p>

<p><a href="http://www.cs.rochester.edu/u/lane/=companion/#list">The Complexity Theory Companion</a> by Hemaspaandra and Ogihara. </p>

<p>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.</p>

CC BY-SA 3.0
2012-07-10T18:55:34.187Z
2012-07-10T18:55:34.187Z
Joshua Grochow
<p>1)R. Lader, N. Lynch, and A. Selman. A comparison of polynomial time reducibilities. Theoretical Computer Science, 1(2):103-124, 1975.<br><br>
2)L.G. Valiant “The complexity of computing the permanent”, Theoretical Computer Science, 8 (1979), pp. 181-201. <br><br>
3)A. Blass &amp; Y. Gurevich “On the unique satisfiability problem.” Information and Control, 55(1-3) pages 80-88, 1982. <br><br>
4)J. Balcazar, R. Book &amp; U. Schoning. “The Polynomial-Time Hierarchy &amp; Sparse Oracles” Journal of the Associate for Computing Machinery, Vol 33, No3. July1986. pages 603-617. <br><br>
5)L.G. Valiant &amp; V. Vazirani “NP is as easy as detecting Unique Solutions” Theoretical Computer Science 47 (1986) pages 85-93.<br><br>
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. <br><br>
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. <br><br>
7)R.Beigel &amp; J. Gill “Counting Classes: Thresholds, parity, Mods, and Fewness” Theoretical Computer Science Volume 103 Pages 3-23. 1992. <br><br>
8)S. Fenner, L. Fortnow &amp; S. Kurtz “Gap-Definable Counting Classes” Journale of Computer And System Sciences Volume 48 Pages 116-148 1994.<br><br>
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. <br><br>
10)B. Borchert, L. Hemaspaandra &amp; J. Rothe “Restrictive Acceptance Suffices for Equivalance Problems”  LMS J Comput. Math 3 Pages 86-95 2000. </p>

CC BY-SA 3.0
2012-07-10T15:26:50.770Z
2012-07-10T15:26:50.770Z
Tayfun Pay
<p>I agree with Abuzer's answer above: I think that every chapter of a computational complexity book (like Arora and Barack's "<a href="http://www.cs.princeton.edu/theory/complexity/">Computational Complexity: a Modern Approach</a>" or Goldreich's "<a href="http://www.wisdom.weizmann.ac.il/~oded/cc-book.html">Computational Complexity: a Conceptual Perspective</a>" ) 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.</p>

<p>However these are my favourites:</p>

<ul>
<li><p><a href="http://en.wikipedia.org/wiki/Savitch%27s_theorem">Savitch's theorem</a>: Savitch, Walter J. (1970), "Relationships between nondeterministic and deterministic tape complexities", Journal of Computer and System Sciences 4 (2): 177–192, <a href="http://dx.doi.org/10.1016/S0022-0000%2870%2980006-X">DOI:10.1016/S0022-0000(70)80006-X</a></p></li>
<li><p><a href="http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem">Cook-Levin theorem</a>: Cook, Stephen (1971). "<a href="http://portal.acm.org/citation.cfm?coll=GUIDE&amp;dl=GUIDE&amp;id=805047">The complexity of theorem proving procedures</a>". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158</p></li>
<li><p>J. Hopcroft, W. Paul, and L. Valiant, <a href="http://dl.acm.org/citation.cfm?id=322015">On time versus space</a>, J. ACM, 24, 332–337 (1977)</p></li>
<li><p>T. P. Baker, J. Gill, R. Solovay. Relativizations of the P =? NP Question. SIAM Journal on Computing, 4(4): 431-442 (1975)</p></li>
</ul>

CC BY-SA 3.0
2012-07-10T14:57:47.543Z
2012-07-10T14:57:47.543Z
Marzio De Biasi
<p>I am starting my PhD this autumn and I am planning to work in complexity theory for my thesis.</p>

<p>I am compiling a list of important papers that every complexity theorist should know.</p>

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

CC BY-SA 3.0
2012-07-09T21:30:48.823Z
Did you already check [What papers should everyone read?](http://cstheory.stackexchange.com/questions/1168/what-papers-should-everyone-read)
Juho
CC BY-SA 3.0
2012-07-10T00:01:45.563Z
Yes. Why is this not just a duplicate of that question.
Suresh Venkat
CC BY-SA 3.0
2012-07-10T00:08:38.237Z
The OP probably just didn't notice that question.
Huck Bennett
CC BY-SA 3.0
2012-07-10T01:37:51.387Z
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
CC BY-SA 3.0
2012-07-10T01:50:15.073Z
I agree with Kaveh.
Mohammad Al-Turkistany
CC BY-SA 3.0
2012-07-10T02:19:00.867Z
@Kaveh The question should be changed to community-wiki and the title adjusted if it is grad-student specific.
Artem Kaznatcheev
CC BY-SA 3.0
2012-07-10T03:07:48.640Z
@Artem, CW set. (the title seems fine to me)
Kaveh
CC BY-SA 3.0
2012-07-10T04:29:12.440Z
@Kaveh: I think this question is subsumed by the other. Many of the answers their are about complexity papers.
Huck Bennett
CC BY-SA 3.0
2012-07-10T07:44:55.783Z
@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
CC BY-SA 3.0
2012-07-12T23:00:21.193Z
@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
CC BY-SA 3.0
2012-09-20T05:20:20.693Z
see also mathoverflow, [What are the most important results (and papers) in complexity theory that every one should know?](http://mathoverflow.net/questions/34487/what-are-the-most-important-results-and-papers-in-complexity-theory-that-every)
vzn
<cc.complexity-theory><reference-request><big-list>
Papers every complexity theorist should read
new grad student
# Papers every complexity theorist should read

(Asked by: username_0 on 2012-07-09)

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.

**Tags:** cc.complexity-theory, reference-request, big-list
> **Comments:**
> **username_1**: Did you already check [What papers should everyone read?](http://cstheory.stackexchange.com/questions/1168/what-papers-should-everyone-read)  
> **username_2**: Yes. Why is this not just a duplicate of that question.  
> **username_3**: The OP probably just didn't notice that question.  
> **username_4**: 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.  
> **username_5**: I agree with Kaveh.  
> **username_6**: @Kaveh The question should be changed to community-wiki and the title adjusted if it is grad-student specific.  
> **username_4**: @Artem, CW set. (the title seems fine to me)  
> **username_3**: @Kaveh: I think this question is subsumed by the other. Many of the answers their are about complexity papers.  
> **username_4**: @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.  
> **username_7**: @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.  
> **username_8**: see also mathoverflow, [What are the most important results (and papers) in complexity theory that every one should know?](http://mathoverflow.net/questions/34487/what-are-the-most-important-results-and-papers-in-complexity-theory-that-every)  

---

## 5 answers

### Answer by username_7 on 2012-07-10. Score: 10

Ryan William's [Non-uniform ACC Circuit Lower Bounds](https://www.stanford.edu/~rrwill/acc-lbs.pdf) 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.

> **Comments:**
> **username_9**: the casual tour is also highly recommended: http://arxiv.org/abs/1111.1261  

---

### Answer by username_10 on 2012-07-10. Score: 9

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

> **[Gems of Theoretical Computer Science](http://www.calvin.edu/~rpruim/publications/gems/)** 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!


---

### Answer by username_7 on 2012-07-10. Score: 7

I'd recommend the results in

[The Complexity Theory Companion](http://www.cs.rochester.edu/u/lane/=companion/#list) 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.


---

### Answer by username_11 on 2012-07-10. Score: 6

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.


---

### Answer by username_12 on 2012-07-10. Score: 5

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](http://www.cs.princeton.edu/theory/complexity/)" or Goldreich's "[Computational Complexity: a Conceptual Perspective](http://www.wisdom.weizmann.ac.il/~oded/cc-book.html)" ) 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](http://en.wikipedia.org/wiki/Savitch%27s_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](http://dx.doi.org/10.1016/S0022-0000%2870%2980006-X)
* [Cook-Levin theorem](http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem): Cook, Stephen (1971). "[The complexity of theorem proving procedures](http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047)". 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](http://dl.acm.org/citation.cfm?id=322015), 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)


---

