Reading

Our favorite papers and books about theory!

Books & chapters

Introduction to the Theory of Computation

Michael Sipser

Formal Language Theory, Recursion Theory, Complexity Theory
Computational Complexity: A Modern Approach

Sanjeev Arora and Boaz Barak

Complexity Theory, Quantum Complexity Theory, Cryptography

Papers

IP = PSPACE: Simplified Proof

Alexander Shen

Complexity Theory, Interactive Proofs
How to Share a Secret

Adi Shamir

Cryptography
Coin Flipping By Telephone

Manuel Blum

Cryptography
One Complexity Theorist's View of Quantum Computing

Lance Fortnow

Quantum Computation, Quantum Complexity Theory