Arora and Barak — Computational Complexity: A Modern Approach

The standard graduate text.

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.

Cook and Nguyen — Logical Foundations of Proof Complexity

Connects bounded arithmetic and propositional proof complexity via two-sorted logic.

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.

Bogdanov and Trevisan — Average-Case Complexity

Survey of average-case complexity and its connections to cryptography and derandomization.

Li and Vitányi — An Introduction to Kolmogorov Complexity and Its Applications

The standard reference on Kolmogorov complexity and algorithmic information theory.

Immerman — Descriptive Complexity

Logical characterizations of complexity classes via finite model theory.

Krajíček — Proof Complexity

The main reference for proof complexity.

Krajíček — Forcing with Random Variables and Proof Complexity

More advanced; connects model theory and forcing to proof complexity.

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.

Savage — Models of Computation

Covers machine models, circuits, and complexity from first principles.

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.

Vadhan — Pseudorandomness

Comprehensive treatment of pseudorandomness, expanders, and derandomization.

Luby and Wigderson — Pairwise Independence and Derandomization

Monograph on pairwise independence and its applications to derandomization.

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.

Cormen et al. — Introduction to Algorithms (CLRS)

The standard algorithms reference.

Roughgarden — Twenty Lectures on Algorithmic Game Theory

Game theory and mechanism design from a TCS perspective.

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.

Katz and Lindell — Introduction to Modern Cryptography

Rigorous and widely used graduate introduction.

Goldreich — Foundations of Cryptography (Vol. 1 & 2)

Thorough theoretical treatment.

Boneh and Shoup — A Graduate Course in Applied Cryptography

Modern and comprehensive; covers both theory and practice.

Pass and Shelat — A Course in Cryptography

Concise graduate-level lecture notes with a rigorous definitional style.

Roth — Introduction to Coding Theory

Rigorous graduate introduction to algebraic coding theory.

Guruswami, Rudra, and Sudan — Essential Coding Theory

Modern treatment oriented toward TCS; covers list decoding and connections to complexity.

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.

Hoory, Linial, and Wigderson — Expander Graphs and their Applications

The standard survey on expander graphs.

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.

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.

Harvard University · Boaz Barak

Graduate Complexity and Foundations

Graduate-level notes on complexity and foundations.

Weizmann Institute of Science · Oded Goldreich

Lecture Notes on Complexity, Cryptography, and Foundations

Notes on complexity, cryptography, and foundations.

The University of Texas at Austin · Scott Aaronson

Computational Complexity

Graduate complexity course notes; broad and philosophically oriented.

University of California, Berkeley · Luca Trevisan

Lecture Notes on Computational Complexity

Concise notes covering the standard complexity curriculum.

Massachusetts Institute of Technology · Scott Aaronson

Great Ideas in Theoretical Computer Science

Broad undergraduate introduction to TCS; accessible and wide-ranging.

Carnegie Mellon University · Ryan O'Donnell

CS Theory Toolkit

Mathematical tools for TCS.

Carnegie Mellon University · Ryan O'Donnell

Analysis of Boolean Functions

Full lecture series to accompany the book.

Carnegie Mellon University · Venkatesan Guruswami

Introduction to Coding Theory

Graduate course notes on algebraic and combinatorial coding theory.

Massachusetts Institute of Technology · Madhu Sudan

Algebra and Computation

Lecture notes on algebraic algorithms: FFT, polynomial identity testing, and coding.

Massachusetts Institute of Technology · Madhu Sudan, Daniel Spielman

Essential Coding Theory

Early version of what became the Guruswami-Rudra-Sudan text; freely available.

University of California, Berkeley · Luca Trevisan

Pseudorandomness and Combinatorial Constructions

Lecture notes on pseudorandomness, extractors, and derandomization.

Stanford University · Dan Boneh

Cryptography

A widely used online introduction to modern cryptography.

Princeton University · Mark Zhandry

Recent Developments in Program Obfuscation

Covers techniques and results in program obfuscation.

Princeton University · Mark Zhandry

Quantum Cryptography

Cryptography in the quantum setting.

University of Waterloo · John Watrous

Theory of Quantum Information

Lecture notes on quantum information theory.

Tata Institute of Fundamental Research · Prahladh Harsha

High-Dimensional Expanders

Lecture and seminar series covering spectral graph theory, high-dimensional expansion, constructions, and applications to codes and PCPs.

Weizmann Institute of Science · Irit Dinur

High-Dimensional Expanders

A graduate course covering combinatorial, topological, and group-theoretic notions of high-dimensional expansion, together with applications to coding and complexity.

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.

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.

Theory of Computing

Diamond open-access TCS journal.

LIPIcs

Open-access conference proceedings in informatics.

STOC

Flagship TCS conference.

FOCS

Flagship TCS conference.

ITCS

Broad TCS conference for exploratory work.

ICALP

Algorithms, complexity, and logic.

MFCS

Mathematical foundations of computer science.

CCC

Complexity theory and proof systems.

SODA

Algorithms and data structures.

APPROX

Approximation algorithms and hardness.

RANDOM

Randomized algorithms and derandomization.

CRYPTO

General cryptography.

EUROCRYPT

General cryptography.

ASIACRYPT

General cryptography.

TCC

Theory of cryptography.

PKC

Public-key cryptography.

LICS

Logic in computer science.

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.

Theory of Computing Blog Aggregator

Aggregates posts from TCS blogs.

TCS+

Online seminar series with recorded talks.

Simons Institute 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.