Textbooks — Complexity Theory

• Arora and Barak — Computational Complexity: A Modern Approach The standard graduate text. Draft freely available.
• Goldreich — Computational Complexity: A Conceptual Perspective Complements Arora-Barak with a more conceptual treatment.
• Papadimitriou — Computational Complexity Older but still a solid reference for NP-completeness and space complexity.
• Wigderson — Mathematics and Computation Broad view of TCS and its connections to mathematics. Freely available.
• Cook and Nguyen — Logical Foundations of Proof Complexity Connects bounded arithmetic and propositional proof complexity via two-sorted logic.

Textbooks — Automata & Computability

• Sipser — Introduction to the Theory of Computation The standard undergraduate introduction to automata, computability, and complexity.
• Hopcroft, Motwani, and Ullman — Introduction to Automata Theory, Languages, and Computation The classical reference on formal languages and automata.
• Soare — Recursively Enumerable Sets and Degrees The standard reference for classical computability theory and degree structures.

Textbooks — Average-Case Complexity & Kolmogorov Complexity

• Bogdanov and Trevisan — Average-Case Complexity Survey of average-case complexity and its connections to cryptography and derandomization. Freely available.
• Li and Vitányi — An Introduction to Kolmogorov Complexity and Its Applications The standard reference on Kolmogorov complexity and algorithmic information theory.

Textbooks — Descriptive Complexity

• Immerman — Descriptive Complexity Logical characterizations of complexity classes via finite model theory.

Textbooks — Proof Complexity

• Krajíček — Proof Complexity The main reference for proof complexity. Covers propositional systems, bounded arithmetic, and lower bounds.
• Krajíček — Forcing with Random Variables and Proof Complexity More advanced; connects model theory and forcing to proof complexity.

Textbooks — Circuit Complexity & Boolean Functions

• Wegener — Complexity Theory Good coverage of circuit complexity and space complexity at the graduate level.
• Jukna — Boolean Function Complexity Thorough treatment of circuit complexity and lower bounds.
• O'Donnell — Analysis of Boolean Functions The standard reference for Fourier analysis on the Boolean cube. Freely available.
• Savage — Models of Computation Covers machine models, circuits, and complexity from first principles. Freely available.

Textbooks — Randomized Algorithms

• Motwani and Raghavan — Randomized Algorithms The classical text on randomized algorithms.
• Mitzenmacher and Upfal — Probability and Computing More accessible than Motwani-Raghavan; good first text on randomized algorithms.

Textbooks — Pseudorandomness & Derandomization

• Vadhan — Pseudorandomness Comprehensive treatment of pseudorandomness, expanders, and derandomization. Freely available.
• Luby and Wigderson — Pairwise Independence and Derandomization Monograph on pairwise independence and its applications to derandomization.

Textbooks — Approximation Algorithms

• Vazirani — Approximation Algorithms Standard graduate text on approximation algorithms.
• Hochbaum (ed.) — Approximation Algorithms for NP-Hard Problems Collected chapters on approximation and inapproximability.
• Williamson and Shmoys — The Design of Approximation Algorithms Modern graduate text on approximation algorithms. Freely available.

Textbooks — Algorithms & Data Structures

• Cormen et al. — Introduction to Algorithms (CLRS) The standard algorithms reference.

Textbooks — Algorithmic Game Theory

• Roughgarden — Twenty Lectures on Algorithmic Game Theory Game theory and mechanism design from a TCS perspective.

Textbooks — Communication Complexity

• Rao and Yehudayoff — Communication Complexity and Applications Modern treatment of communication complexity.
• Kushilevitz and Nisan — Communication Complexity The original graduate text on communication complexity; still widely used.

Textbooks — Cryptography

• Katz and Lindell — Introduction to Modern Cryptography Rigorous and widely used graduate introduction.
• Goldreich — Foundations of Cryptography (Vol. 1 & 2) Thorough theoretical treatment. Does not cover recent developments.
• Boneh and Shoup — A Graduate Course in Applied Cryptography Modern and comprehensive; covers both theory and practice. Freely available.
• Pass and Shelat — A Course in Cryptography Concise graduate-level lecture notes with a rigorous definitional style. Freely available.

Textbooks — Coding Theory

• Roth — Introduction to Coding Theory Rigorous graduate introduction to algebraic coding theory. Freely available.
• Guruswami, Rudra, and Sudan — Essential Coding Theory Modern treatment oriented toward TCS; covers list decoding and connections to complexity. Freely available.

Textbooks — Combinatorics & Probabilistic Methods

• Alon and Spencer — The Probabilistic Method The definitive reference on the probabilistic method.
• Jukna — Extremal Combinatorics Combinatorial tools used throughout TCS.
• Graham, Knuth, and Patashnik — Concrete Mathematics Mathematical foundations for computer science.
• Diestel — Graph Theory The standard graduate reference on graph theory. Freely available online.

Textbooks — Expander Graphs

• Hoory, Linial, and Wigderson — Expander Graphs and their Applications The standard survey on expander graphs. Freely available.

Textbooks — Logic & Foundations

• Enderton — A Mathematical Introduction to Logic Standard introductory text on first-order logic and model theory.
• Enderton — Elements of Set Theory Rigorous introduction to axiomatic set theory.
• Shoenfield — Mathematical Logic Classical graduate text; strong on proof theory and recursion theory.
• Marker — Model Theory: An Introduction Standard graduate introduction to model theory; useful for finite model theory connections.
• Ebbinghaus and Flum — Finite Model Theory The standard reference for finite model theory; closely connected to descriptive complexity.

Textbooks — Quantum

• Nielsen and Chuang — Quantum Computation and Quantum Information The standard textbook.
• Aaronson — Quantum Computing Since Democritus More informal and broader in scope; good complement to Nielsen-Chuang.
• Wilde — Quantum Information Theory Rigorous treatment of quantum Shannon theory; second edition freely available.

Courses & Lecture Notes — Complexity

• Barak — Graduate Complexity and Foundations Course notes from Barak's graduate TCS courses.
• Goldreich — Lecture Notes Notes on complexity, cryptography, and foundations.
• Aaronson — Computational Complexity (UT Austin) Graduate complexity course notes; broad and philosophically oriented.
• Trevisan — Lecture Notes on Computational Complexity Concise notes covering the standard complexity curriculum.
• Aaronson — Great Ideas in Theoretical Computer Science (MIT OCW, 2008) Broad undergraduate introduction to TCS; accessible and wide-ranging.

Courses & Lecture Notes — Boolean Functions & Combinatorics

• O'Donnell — CS Theory Toolkit (CMU) Mathematical tools for TCS.
• O'Donnell — Analysis of Boolean Functions (CMU, video lectures) Full lecture series to accompany the book.

Courses & Lecture Notes — Coding Theory

• Guruswami — Introduction to Coding Theory (CMU) Graduate course notes on algebraic and combinatorial coding theory.
• Sudan — Algebra and Computation (MIT) Lecture notes on algebraic algorithms: FFT, polynomial identity testing, and coding.
• Sudan and Spielman — Essential Coding Theory (MIT OCW, 2004) Early version of what became the Guruswami-Rudra-Sudan text; freely available.

Courses & Lecture Notes — Pseudorandomness

• Trevisan — Pseudorandomness and Combinatorial Constructions Lecture notes on pseudorandomness, extractors, and derandomization.

Courses & Lecture Notes — Cryptography

• Boneh — Cryptography (Stanford, online) The widely used online cryptography course by Dan Boneh.
• Zhandry — Recent Developments in Program Obfuscation (Princeton) Covers techniques and results in program obfuscation.
• Zhandry — Quantum Cryptography (Princeton) Cryptography in the quantum setting.

Courses & Lecture Notes — Quantum

• Watrous — Theory of Quantum Information Lecture notes on quantum information theory.

Preprint Servers

• ECCC Preprints in computational complexity.
• arXiv — cs.CC, cs.DS, cs.LO, cs.CR General preprint server for TCS and cryptography.
• IACR ePrint Preprints in cryptography.

Conferences — General TCS

• STOC ACM Symposium on Theory of Computing. One of the two flagship TCS venues.
• FOCS IEEE Symposium on Foundations of Computer Science. The other flagship TCS venue.
• ITCS — Innovations in Theoretical Computer Science Newer venue; encourages speculative and exploratory work.
• ICALP — International Colloquium on Automata, Languages and Programming The main EATCS conference, covering algorithms, complexity, and logic.
• MFCS — Mathematical Foundations of Computer Science Annual conference on mathematical aspects of TCS.

Conferences — Complexity & Proof Systems

• CCC — Computational Complexity Conference The dedicated complexity theory conference.

Conferences — Algorithms & Combinatorics

• SODA — ACM-SIAM Symposium on Discrete Algorithms Top venue for algorithms and data structures.
• APPROX — Approximation Algorithms for Combinatorial Optimization Problems Annual workshop on approximation algorithms and hardness of approximation.
• RANDOM — Randomization and Computation Annual workshop on randomized algorithms and derandomization. Co-located with APPROX.

Conferences — Cryptography

• IACR Conferences — CRYPTO, EUROCRYPT, ASIACRYPT, TCC The main IACR venues.

Conferences — Logic

• LICS — Symposium on Logic in Computer Science Top venue for logic in computer science.

Blogs

• Shtetl-Optimized Scott Aaronson on quantum computing and complexity theory.
• Gödel's Lost Letter and P=NP Dick Lipton and Ken Regan on complexity theory.
• Windows On Theory Boaz Barak on complexity, cryptography, and ML theory.
• Computational Complexity Lance Fortnow and Bill Gasarch on complexity theory.
• In Theory Luca Trevisan on complexity, pseudorandomness, and combinatorics.
• Goldreich — My Choices Goldreich's curated reading list.

Reference & Q&A

• TCS Stack Exchange Q&A for TCS researchers and students.
• Cryptography Stack Exchange Q&A for cryptography.
• The Complexity Zoo Catalogue of complexity classes.
• DBLP Bibliography database for CS. Useful for author and paper lookups.

Communities & Aggregators

• Theory of Computing Blog Aggregator Aggregates posts from TCS blogs.
• TCS+ Online seminar series with recorded talks.
• Simons Institute — Lecture Videos Recorded workshops and talks from the Simons Institute.
• SIGACT ACM Special Interest Group on Algorithms and Computation Theory.
• IACR International Association for Cryptologic Research.