## The Complexity Theory Reading Challenge

I have been masquerading as a complexity theorist for quite some time now, and I realized that it was time I learnt the basics. The challenge is to read some of the most influential works in complexity theory, this includes books, surveys, and original results. Feel free to join in on the challenge. You can update on your progress or suggest new works in the comments below, or on Twitter with the far-too-long hashtag #ComplexityTheoryReadingChallenge. [S; August 3, 2019]

Note. Some of the stuff is not strictly complexity theory, but interesting nonetheless.

#### Selected Entries from Scott’s Chicken Soup for the Complexity Soul

• Computational Complexity, by Christos Papadimitriou
• I have skimmed parts of this book when I still loaned physical books from the Waterloo library. I need to go back and read the whole thing.
• Gems of Theoretical Computer Science by Uwe Schöning and Randall Pruim
• I read the chapter on PAC learning back in 2016 but I haven’t looked at it since.
• I love the format. It would be nice to have a gems of quantum computing book that covers the threshold theorem, early results in query complexity, Hamiltonian simulation stuff, the algorithm for Jones polynomial, and stuff like that.
• Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak
• I have read selected chapters of this book. I might take a graduate complexity course on this book.
• Quantum Computation, by John Preskill
• These are online lecture notes, here is a link.
• I have read parts of chapter 9 and 10. I found those chapters a little too high-level but that is probably because I read way too many papers on those topics.
• Quantum Computation, by Umesh Vazirani
• These are online lecture notes, here is a link.
• I really understood Simon’s algorithm after reading Vazirani’s lecture on it.
• Lecture Notes on Computational Complexity, by Luca Trevisan
• Cryptography, by Luca Trevisan
• By now, I should know the stuff in the earlier chapters, but the stuff in the later chapters looks awesome. Imma hold off till after the crypto course I am taking in the Fall (2019).
• Combinatorial Optimization, by Luca Trevisan
• I read parts of the last chapter to understand matrix multiplicative weights.
• Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan
• I saw the cover of this book in the TCS section at the library…
• Computers and Intractability, by Michael Garey and David Johnson
• I stumbled upon it at the library and read a few sections. It is a big book.
• An Introduction to Computational Learning Theory, by Michael Kearns and Umesh Vazirani
• I almost paid a library late fee for this book!!
• It is short and awesome. I highly recommend it to anyone interested in CLT.
• Artificial Intelligence, by Stuart Russell and Peter Norvig
• I am not big into classical AI but I should check this book out.
• Complexity and Real Computation, by Lenore Blum, Felix Cucker, Michael Shub, and Steve Smale
• I love the cover!! A bonus question in my intro-TCS course almost made me read it.
• The Art of Computer Programming, by Donald Knuth
• I bought volume 1 because I could get a DRM-free pdf.
• Don’t let the MMIX stop you, it is fucking beautiful. Stop reading this list, and go read TAoCP.
• Set Theory and the Continuum Hypothesis, by Paul Cohen
• I tried reading this book three times, but I haven’t made much progress. The book is short and seems easy but don’t be fooled, it is a hard read, you need a pen and paper to follow.
• The Road to Reality, by Roger Penrose
• Don’t be fooled by the cover or the price tag—his is not a bedtime book. Hence I haven’t made much progress.

#### More Books

• Mathematics and Computation, by Avi Wigderson
• I read sections of this book, and I love it.
• The script font for complexity classes bothers me.

#### Some Papers

• IP = SPACE: simplified proof, by A. Shen