<p>Joshua Grochow gave a very detailed list in his <a href="https://cstheory.stackexchange.com/a/53236/47855">answer</a>.</p>
<p>I would like to mention a few sources that present more introductory/intermediate material, although these may not be useful for OP (hopefully, useful to a future reader). Arora-Barak's textbook is good for this purpose. Also see the books <em>Structural Complexity I</em> [1] and <em>Structural Complexity II</em> [2] by  Balcázar, Díaz and Gabarró, and the references therein (bibliographical remarks at chapter endings). For books specifically on FPT, see answers to this <a href="https://cstheory.stackexchange.com/q/4891/47855">question</a>.</p>
<p>There are dedicated books and surveys on many sub-topics. E.g.:  the book on Kolmogorov complexity by Li and Vitányi [3], and this artcile on relativizing complexity classes [4].</p>
<h2>References</h2>
<p>[1]
<em>Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim</em>, Structural complexity. I, EATCS Monographs on Theoretical Computer Science, Vol. 11. Berlin etc.: Springer-Verlag. IX, 191 p., DM 54.00 (1988). <a href="https://zbmath.org/?q=an:0638.68040" rel="nofollow noreferrer">ZBL0638.68040</a>.</p>
<p>[2]
<em>Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim</em>, Structural complexity II, EATCS Monographs on Theoretical Computer Science. 22. Berlin etc.: Springer-Verlag. IX, 283 p. (1990). <a href="https://zbmath.org/?q=an:0746.68032" rel="nofollow noreferrer">ZBL0746.68032</a>.  <a href="https://cstheory.stackexchange.com/a/53236/47855">1</a>: <a href="https://cstheory.stackexchange.com/a/53236/47855">https://cstheory.stackexchange.com/a/53236/47855</a></p>
<p>[3]
<em>Li, Ming; Vitányi, Paul M. B.</em>, <a href="https://doi.org/10.1007/978-3-030-11298-1" rel="nofollow noreferrer"><strong>An introduction to Kolmogorov complexity and its applications</strong></a>, Texts in Computer Science. Cham: Springer (ISBN 978-3-030-11297-4/hbk; 978-3-030-11298-1/ebook). xxii, 834 p. (2019). <a href="https://zbmath.org/?q=an:1423.68005" rel="nofollow noreferrer">ZBL1423.68005</a>.</p>
<p>[4]
<em>Aehlig, Klaus; Cook, Stephen; Nguyen, Phuong</em>, <a href="https://doi.org/10.1007/s00037-015-0113-8" rel="nofollow noreferrer"><strong>Relativizing small complexity classes and their theories</strong></a>, Comput. Complexity 25, No. 1, 177-215 (2016). <a href="https://zbmath.org/?q=an:1336.68084" rel="nofollow noreferrer">ZBL1336.68084</a>.</p>

CC BY-SA 4.0
2023-08-24T09:36:46.810Z
2023-08-24T09:36:46.810Z
Cyriac Antony
<p>Another quite comprehensive textbook that was not mentioned in the earlier answers is this:</p>
<p>Theory of Computational Complexity, by Ding-Zhu Du and Ker-I Ko. Here is the Amazon link to the book:</p>
<p><a href="https://rads.stackoverflow.com/amzn/click/com/1118306082" rel="nofollow noreferrer" rel="nofollow noreferrer">https://www.amazon.com/Computational-Complexity-Discrete-Mathematics-Optimization/dp/1118306082/ref=sr_1_2?crid=2QSXN3AF6QWPD&amp;keywords=Theory+of+Computational+Complexity&amp;qid=1692932876&amp;s=books&amp;sprefix=theory+of+computational+complexity%2Cstripbooks%2C197&amp;sr=1-2&amp;ufe=app_do%3Aamzn1.fos.f5122f16-c3e8-4386-bf32-63e904010ad0</a></p>

CC BY-SA 4.0
2023-08-25T03:20:24.967Z
2023-08-25T03:20:24.967Z
Andras Farago
<p>I don't think there really are <em>canonical</em> references for this stuff (roughly: advanced modern structural complexity theory), but here are some references. This list is partially geared towards my tastes (but only partially), and far from exhaustive, even within my favorite subjects. (Apologies to anyone omitted - nothing implied by that other than lack of time to think and write.)</p>
<p>More modern / currently in vogue topics in structural complexity include:</p>
<ul>
<li>Meta-complexity. Keywords to look up: natural proofs, derandomization, circuit learning, minimimum circuit size problem (MCSP). People to look up: Ryan Williams, Marco Carmosino, Shuichi Hirahara, Rahul Ilango, Igor Oliveira, Eric Allender, Antonina Kolokolova, Valentine Kabanets. Some of this was <a href="https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/" rel="nofollow noreferrer">highlighted recently in Quanta</a> (with additional links to papers therein).</li>
<li>There are a variety of nice open questions in Allender's <a href="https://doi.org/10.1145/3586165.3586174" rel="nofollow noreferrer">&quot;Parting Thoughts and Parting Shots&quot;</a></li>
<li>Derandomization. <a href="https://doi.org/10.1145/1391289.1391291" rel="nofollow noreferrer">L=SL</a> (if you haven't seen it). Work towards derandomizing RL or BPL, e.g. <a href="https://doi.org/10.1145/3055399.3055414" rel="nofollow noreferrer">Hoza &amp; Umans</a> and refs therein and thereto.</li>
<li>Fine-grained complexity. Lookup the work of <a href="https://people.csail.mit.edu/virgi/" rel="nofollow noreferrer">Virginia Vassilevska Williams</a>. Also here's a <a href="https://doi.org/10.4230/LIPIcs.STACS.2019.4" rel="nofollow noreferrer">tutorial by Bringmann</a>.</li>
<li>Quantum complexity (e.g. <a href="https://doi.org/10.1145/2049697.2049704" rel="nofollow noreferrer">QIP=PSPACE</a>, <a href="https://cacm.acm.org/magazines/2021/11/256404-mip-re/fulltext" rel="nofollow noreferrer">MIP*=CE</a>, <a href="https://doi.org/10.1145/3313276.3316315" rel="nofollow noreferrer">oracle separating BQP from PH</a>)</li>
<li>There's a lot going on with circuit complexity and analysis of Boolean functions, but it's not exactly &quot;complexity classes&quot; so I don't know if it counts for your question. Here are a few pointers: <a href="http://www.cs.cmu.edu/%7Eodonnell/papers/Analysis-of-Boolean-Functions-by-Ryan-ODonnell.pdf" rel="nofollow noreferrer">Ryan O'Donnell's book</a>, <a href="https://doi.org/10.1007/978-3-642-24508-4" rel="nofollow noreferrer">Stasys Jukna's book</a>, <a href="https://doi.org/10.4007/annals.2019.190.3.6" rel="nofollow noreferrer">Huang's resolution of the sensitivity conjecture</a>, advances in and around combinatorial sunflowers (e.g. <a href="https://doi.org/10.4007/annals.2021.194.3.5" rel="nofollow noreferrer">improved bounds for the sunflower lemma</a>), <a href="https://doi.org/10.4230/LIPIcs.CCC.2017.15" rel="nofollow noreferrer">tight bounds on the Fourier spectrum of <span class="math-container">$\mathsf{AC}^0$</span></a>, etc.</li>
<li>Algebraic (/geometric) complexity theory is its whole own area that also has lots going on, but I don't know how much of it you'd consider &quot;structural&quot;. One relatively recent big structural result is that all polysize formulas can be approximated infinitesimally closely by width-2 algebraic branching programs <a href="https://doi.org/10.1145/3209663" rel="nofollow noreferrer">Bringmann-Ikenmeyer-Zuiddam</a>. Also stuff happening here around algebraic natural proofs, e.g. here's a recent <a href="https://doi.org/10.1145/3510382.3510392" rel="nofollow noreferrer">survey by Volk</a>. (This area also has the tightest connections to algebraic geometry, so you might be interested.)</li>
</ul>
<p>For a bit older complexity class stuff (not exactly outdated, just much of it is not currently &quot;hot&quot; areas of research, though there are plenty of open questions), here are some books I like:</p>
<ul>
<li>Hemaspaandra &amp; Ogihara, <a href="https://doi.org/10.1007/978-3-662-04880-1" rel="nofollow noreferrer">Complexity Theory Companion</a></li>
<li>Schöning, <a href="https://doi.org/10.1007/3-540-16079-5" rel="nofollow noreferrer">Complexity and Structure</a></li>
<li>Schöning and Pruim, <a href="https://doi.org/10.1007/978-3-642-60322-8" rel="nofollow noreferrer">Gems of Theoretical Computer Science</a></li>
<li>Hemaspaandra and Torenvliet, <a href="https://doi.org/10.1007/978-3-662-05080-4" rel="nofollow noreferrer">Theory of Semi-Feasible Algorithms</a></li>
</ul>

CC BY-SA 4.0
2023-08-24T05:17:29.237Z
Thank you for such a detailed response — I'm excited to take a look at everything you mentioned!
LiminalSpace
CC BY-SA 4.0
2023-08-23T22:03:56.600Z
2023-08-24T18:28:26.797Z
2023-08-24T18:28:26.797Z
Joshua Grochow
<p>I'm a PhD student in mathematics (mostly studying algebraic geometry), but I've always been interested in computational complexity theory.</p>
<p>As an undergraduate, I completed an independent reading course covering Arora-Barak's textbook on computational complexity, culminating the proof of the <span class="math-container">$\mathsf{PCP}$</span> theorem. It's been a little bit, but I remember really enjoying the sections on the polynomial hierarchy and interactive proofs (leading to a proof that <span class="math-container">$\mathsf{IP}=\mathsf{PSPACE}$</span>).</p>
<p>I'd love to learn more about structural complexity theory, so (paraphrasing Wikipedia) the study of complexity classes themselves, rather than specific algorithms.</p>
<p>Are there any canonical references for this type of material? I'd also be really interested in learning more about what problems structural complexity theorists study today. (With a quick Google search, it seems like most articles that come up are from the 80's and 90's.)</p>
<p>Thank you for any help!</p>

<cc.complexity-theory><reference-request><complexity-classes><polynomial-hierarchy>
Structural Complexity Theory References
LiminalSpace
# Structural Complexity Theory References

(Asked by: username_0 on 2023-08-20)

I'm a PhD student in mathematics (mostly studying algebraic geometry), but I've always been interested in computational complexity theory.

As an undergraduate, I completed an independent reading course covering Arora-Barak's textbook on computational complexity, culminating the proof of the $\mathsf{PCP}$ theorem. It's been a little bit, but I remember really enjoying the sections on the polynomial hierarchy and interactive proofs (leading to a proof that $\mathsf{IP}=\mathsf{PSPACE}$).

I'd love to learn more about structural complexity theory, so (paraphrasing Wikipedia) the study of complexity classes themselves, rather than specific algorithms.

Are there any canonical references for this type of material? I'd also be really interested in learning more about what problems structural complexity theorists study today. (With a quick Google search, it seems like most articles that come up are from the 80's and 90's.)

Thank you for any help!

**Tags:** cc.complexity-theory, reference-request, complexity-classes, polynomial-hierarchy

---

## 3 answers

### Answer by username_3 on 2023-08-23. Score: 15 | Accepted answer

I don't think there really are *canonical* references for this stuff (roughly: advanced modern structural complexity theory), but here are some references. This list is partially geared towards my tastes (but only partially), and far from exhaustive, even within my favorite subjects. (Apologies to anyone omitted - nothing implied by that other than lack of time to think and write.)

More modern / currently in vogue topics in structural complexity include:

* Meta-complexity. Keywords to look up: natural proofs, derandomization, circuit learning, minimimum circuit size problem (MCSP). People to look up: Ryan Williams, Marco Carmosino, Shuichi Hirahara, Rahul Ilango, Igor Oliveira, Eric Allender, Antonina Kolokolova, Valentine Kabanets. Some of this was [highlighted recently in Quanta](https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/) (with additional links to papers therein).
* There are a variety of nice open questions in Allender's ["Parting Thoughts and Parting Shots"](https://doi.org/10.1145/3586165.3586174)
* Derandomization. [L=SL](https://doi.org/10.1145/1391289.1391291) (if you haven't seen it). Work towards derandomizing RL or BPL, e.g. [Hoza & Umans](https://doi.org/10.1145/3055399.3055414) and refs therein and thereto.
* Fine-grained complexity. Lookup the work of [Virginia Vassilevska Williams](https://people.csail.mit.edu/virgi/). Also here's a [tutorial by Bringmann](https://doi.org/10.4230/LIPIcs.STACS.2019.4).
* Quantum complexity (e.g. [QIP=PSPACE](https://doi.org/10.1145/2049697.2049704), [MIP\*=CE](https://cacm.acm.org/magazines/2021/11/256404-mip-re/fulltext), [oracle separating BQP from PH](https://doi.org/10.1145/3313276.3316315))
* There's a lot going on with circuit complexity and analysis of Boolean functions, but it's not exactly "complexity classes" so I don't know if it counts for your question. Here are a few pointers: [Ryan O'Donnell's book](http://www.cs.cmu.edu/%7Eodonnell/papers/Analysis-of-Boolean-Functions-by-Ryan-ODonnell.pdf), [Stasys Jukna's book](https://doi.org/10.1007/978-3-642-24508-4), [Huang's resolution of the sensitivity conjecture](https://doi.org/10.4007/annals.2019.190.3.6), advances in and around combinatorial sunflowers (e.g. [improved bounds for the sunflower lemma](https://doi.org/10.4007/annals.2021.194.3.5)), [tight bounds on the Fourier spectrum of $\mathsf{AC}^0$](https://doi.org/10.4230/LIPIcs.CCC.2017.15), etc.
* Algebraic (/geometric) complexity theory is its whole own area that also has lots going on, but I don't know how much of it you'd consider "structural". One relatively recent big structural result is that all polysize formulas can be approximated infinitesimally closely by width-2 algebraic branching programs [Bringmann-Ikenmeyer-Zuiddam](https://doi.org/10.1145/3209663). Also stuff happening here around algebraic natural proofs, e.g. here's a recent [survey by Volk](https://doi.org/10.1145/3510382.3510392). (This area also has the tightest connections to algebraic geometry, so you might be interested.)

For a bit older complexity class stuff (not exactly outdated, just much of it is not currently "hot" areas of research, though there are plenty of open questions), here are some books I like:

* Hemaspaandra & Ogihara, [Complexity Theory Companion](https://doi.org/10.1007/978-3-662-04880-1)
* Schöning, [Complexity and Structure](https://doi.org/10.1007/3-540-16079-5)
* Schöning and Pruim, [Gems of Theoretical Computer Science](https://doi.org/10.1007/978-3-642-60322-8)
* Hemaspaandra and Torenvliet, [Theory of Semi-Feasible Algorithms](https://doi.org/10.1007/978-3-662-05080-4)

> **Comments:**
> **username_0**: Thank you for such a detailed response — I'm excited to take a look at everything you mentioned!  

---

### Answer by username_1 on 2023-08-24. Score: 3

Joshua Grochow gave a very detailed list in his [answer](https://cstheory.stackexchange.com/a/53236/47855).

I would like to mention a few sources that present more introductory/intermediate material, although these may not be useful for OP (hopefully, useful to a future reader). Arora-Barak's textbook is good for this purpose. Also see the books *Structural Complexity I* [1] and *Structural Complexity II* [2] by Balcázar, Díaz and Gabarró, and the references therein (bibliographical remarks at chapter endings). For books specifically on FPT, see answers to this [question](https://cstheory.stackexchange.com/q/4891/47855).

There are dedicated books and surveys on many sub-topics. E.g.: the book on Kolmogorov complexity by Li and Vitányi [3], and this artcile on relativizing complexity classes [4].

## References

[1]
*Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim*, Structural complexity. I, EATCS Monographs on Theoretical Computer Science, Vol. 11. Berlin etc.: Springer-Verlag. IX, 191 p., DM 54.00 (1988). [ZBL0638.68040](https://zbmath.org/?q=an:0638.68040).

[2]
*Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim*, Structural complexity II, EATCS Monographs on Theoretical Computer Science. 22. Berlin etc.: Springer-Verlag. IX, 283 p. (1990). [ZBL0746.68032](https://zbmath.org/?q=an:0746.68032). [1](https://cstheory.stackexchange.com/a/53236/47855): <https://cstheory.stackexchange.com/a/53236/47855>

[3]
*Li, Ming; Vitányi, Paul M. B.*, [**An introduction to Kolmogorov complexity and its applications**](https://doi.org/10.1007/978-3-030-11298-1), Texts in Computer Science. Cham: Springer (ISBN 978-3-030-11297-4/hbk; 978-3-030-11298-1/ebook). xxii, 834 p. (2019). [ZBL1423.68005](https://zbmath.org/?q=an:1423.68005).

[4]
*Aehlig, Klaus; Cook, Stephen; Nguyen, Phuong*, [**Relativizing small complexity classes and their theories**](https://doi.org/10.1007/s00037-015-0113-8), Comput. Complexity 25, No. 1, 177-215 (2016). [ZBL1336.68084](https://zbmath.org/?q=an:1336.68084).


---

### Answer by username_2 on 2023-08-25. Score: 1

Another quite comprehensive textbook that was not mentioned in the earlier answers is this:

Theory of Computational Complexity, by Ding-Zhu Du and Ker-I Ko. Here is the Amazon link to the book:

[https://www.amazon.com/Computational-Complexity-Discrete-Mathematics-Optimization/dp/1118306082/ref=sr\_1\_2?crid=2QSXN3AF6QWPD&keywords=Theory+of+Computational+Complexity&qid=1692932876&s=books&sprefix=theory+of+computational+complexity%2Cstripbooks%2C197&sr=1-2&ufe=app\_do%3Aamzn1.fos.f5122f16-c3e8-4386-bf32-63e904010ad0](https://rads.stackoverflow.com/amzn/click/com/1118306082)


---

