6
$\begingroup$

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!

$\endgroup$

3 Answers 3

13
+50
$\begingroup$

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:

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:

$\endgroup$
1
  • $\begingroup$ Thank you for such a detailed response — I'm excited to take a look at everything you mentioned! $\endgroup$ Aug 24, 2023 at 5:17
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\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.