Structural Complexity Theory References

Question

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!

Answer 1

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 (with additional links to papers therein).
• There are a variety of nice open questions in Allender's "Parting Thoughts and Parting Shots"
• Derandomization. L=SL (if you haven't seen it). Work towards derandomizing RL or BPL, e.g. Hoza & Umans and refs therein and thereto.
• Fine-grained complexity. Lookup the work of Virginia Vassilevska Williams. Also here's a tutorial by Bringmann.
• Quantum complexity (e.g. QIP=PSPACE, MIP*=CE, oracle separating BQP from PH)
• 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, Stasys Jukna's book, Huang's resolution of the sensitivity conjecture, advances in and around combinatorial sunflowers (e.g. improved bounds for the sunflower lemma), tight bounds on the Fourier spectrum of $\mathsf{AC}^0$, 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. Also stuff happening here around algebraic natural proofs, e.g. here's a recent survey by Volk. (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
• Schöning, Complexity and Structure
• Schöning and Pruim, Gems of Theoretical Computer Science
• Hemaspaandra and Torenvliet, Theory of Semi-Feasible Algorithms

Answer 2

Joshua Grochow gave a very detailed list in his answer.

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.

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.

[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. 1: https://cstheory.stackexchange.com/a/53236/47855

[3] Li, Ming; Vitányi, Paul M. B., An introduction to Kolmogorov complexity and its applications, 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.

[4] Aehlig, Klaus; Cook, Stephen; Nguyen, Phuong, Relativizing small complexity classes and their theories, Comput. Complexity 25, No. 1, 177-215 (2016). ZBL1336.68084.

Answer 3

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