Resources

This page contains resources on Theoretical Computer Science that I have encountered at some point. It is biased towards those that generally emphasize clarity of exposition over technical detail (according to me ofcourse!) It is mainly for my reference. Others might find it helpful too.

Books

• Introduction to the Theory of Computation - Michael Sipser
• Quantum Computing since Democritus - Scott Aaronson
• Nature of Computation - Cristopher Moore and Stephan Mertens
• Quantum Computer Science - David Mermin
• Extremal Combinatorics - Stasys Jukna
• Introduction to Computational Learning Theory - Michael Kearns and Umesh Vazirani

Courses and Lecture Notes

• Algorithms - Jeff Erickson
• Probability and Computing - Ryan O’Donnell
• Introduction to Quantum Information Science - Scott Aaronson
• Computational Complexity - Luca Trevisan

Articles/Blog Posts

• Razborov’s Method of Approximations - Timothy Gowers
• BGS Relativisation - Terence Tao
• From Cbits to Qbits - David Mermin
• Complexity Theorist’s view of Quantum Computing - Lance Fortnow
• Quantum Computing for the very curious - Andy Matuschak and Michael Nielsen
• Shor’s Factorization Algorithm - Scott Aaronson
• Favorite Theorems - Lance Fortnow
• Two Proofs of Ladner’s Theorem - Lance Fortnow
• On the Sensitivity Conjecture - Terence Tao
• Dvir’s proof of the finite field Kakeya conjecture - Terence Tao