Theory Courses with Extensive Lecture Notes or Linked Papers
- Cryptography/computer security
- New Developments in Cryptography, by Barak, Goldwasser, Kalai, Reyzin, and Vadhan
- Introduction to Cryptography and Foundations of Cryptography,
by Lindell
- *Introduction to cryptography (fall '94), by Rafail Ostrovsky
- Public-key cryptography, by Adi Shamir (incl. lattice-based crypto)
- Lattices in cryptography, by Nguyen (mainly links); see also here for more links
- Advanced cryptography, by Lokam (incl. lattice-based crypto)
- Advanced topics in cryptography, by Canetti and Goldwasser
- Cryptography, by David Wagner and Luca Trevisan
- Cryptography, by Yevgeniy Dodis
- Undergraduate cryptography and Advanced topics in cryptography, by Jonathan Katz
- Cryptography by Anna Lysyanskaya (MIT)
- *Advanced cryptography, by Silvio Micali
- Cryptography, by Leo Reyzin
- Cryptologic protocol design, by Ivan Damgård and Ronald Cramer
- Advanced cryptography, by Daniele Micciancio
- Cryptography and Data Security, by Michael Fischer
- Networking theory
- Complexity theory and related topics (for PCP and coding theory, see below)
- Computational complexity, by Kristoffer Arnsfelt Hansen
- notes from lecture at Clay Math Institute, by Barrington and Maciel
- Lecture notes on complexity theory: a survey, notes from 2002 and *notes from 1999, by Oded Goldreich (see also here)
- Complexity theory (multiple semesters), by Luca Trevisan (*Spring '01, *Fall '02) and complexity theory (Fall '04). Also Spring 2008
- *Advanced complexity theory, by Impagliazzo
- *Complexity theory, by Sanjeev Arora
- Expanders in CS, by Dwork and Harsha
- Complexity theory (slides only), by Chris Umans (but see also here)
- *Complexity theory, by Jaikumar Radhakrishnan and Sanjeev Saluja
- *Pairwise independence and derandomization (notes), by Michael Luby and Avi Wigderson
- *Computational complexity theory, by Steven Rudich
- Complexity theory, by Barak
- Computational complexity theory, by Barrington and Maciel
- Fundamentals of computing, by Leonid Levin
- *Introduction to complexity theory, *advanced complexity theory, and randomness and complexity, by Jin-Yi Cai
- Pseudorandomness: *Spring 2001 (lecture notes) and Spring 2003 (references/links only), by David Zuckerman
- *Pseudorandomness and computational complexity, by Salil Vadhan
- *Randomness and derandomization and *advanced complexity theory, by Dieter van Melkebeek
- Complexity theory (Spring 2002) and *Spring 2004, by Dexter Kozen
- Complexity theory, by Miltersen
- Combinatorial methods with applications to circuit complexity, by Jukna
- *Complexity of computation and *combinatorial methods in complexity theory, by Eric Allender
- *Probabilistic algorithms and pseudorandom generators and *complexity theory, by Martin Tompa
- Advanced complexity theory: Spring 2003, *Spring 2002, and Spring 2005, by Madhu Sudan
- Avanced computational complexity theory, by Safra (slides only)
- Computational Complexity, by Lovasz and Gacs
- Advanced complexity theory: *2001, *2000, *1999, and *1997-1998, by Dan Spielman (see also *here for better notes for 2001)
- *Complexity theory (notes), by Johan Hastad
- *Computational complexity, by Micah Adler
- *Computational complexity and *pseudorandomness, by Valentine Kabanets
- Advances in complexity, by Sitharam
- Complexity theory, by Lokam
- Fourier transforms..., by Vazirani
- Computational complexity essentials, by Beame
- Harmonic analysis for complexity theorists, by Linial
- Courses focused on the PCP theorem
- *Interactive proofs and PCP, by Jaikumar Radhakrishnan and Sanjeev Saluja
- *The PCP theorem, by Uriel Feige
- The PCP theorem, by Subhash Khot
- *Probabilistically checkable proofs, by Madhu Sudan
- *Probabilistically checkable proofs..., by Hougardy, Promel, and Steger
- PCP..., by Irit Dinur
PCP and Hardness of Approximation, by Trevisan
- Probabilistic proofs and PCP, by Jiri Sgall
- Coding theory and related topics
- *Introduction to coding theory, by Jon Feldman
- Coding theory and complexity theory, by Luca Trevisan
- Error-correcting codes, by Rudra
- Coding theory and Codes and pseudorandom objects, by Venkatesan Guruswami
- *Algorithmic introduction to coding theory and essential coding theory *2002 and 2004, by Madhu Sudan
- Complexity issues in coding theory (survey), by Alex Barg
- Expander graphs and their applications, by Nati Linial and Avi Wigderson
- Expander graphs and applications (mostly links to other notes), by Shlomo Hoory
- *Coding theory, by Elchanan Mossel and Chris Umans
- Advanced topics in coding theory, by Alex Barg
- Algorithms
- Algorithms
- Mitzenmacher's class
- Geometric methods..., by Rabani
- Algorithmist's Toolkit, by Kelner
- Probabiliy and Algorithms, by Schulman
- Randomized algorithms, by Gupta and Chawla
- Sublinear time algorithms, F04 and S07, by Ronitt Rubinfeld
- Randomness and computation, S06 and S08, by Ronitt Rubinfeld
- Randomized methods in computation, by Oded Goldreich
- Parallel algorithms, by Christos Papadimitriou and Satish Rao
- Advanced algorithms, by Rajeev Motwani
- Advanced algorithms, by Michel Goemans. Some misc. notes are also available
- Randomized algorithms and advanced algorithms, by David Karger
- Advanced algorithms, by Micah Adler. Notes from previous semesters are also available: Fall 2002, Fall 2001, Fall 2000
- Really advanced algorithms, by Micah Adler
- Combinatorial algorithms (undergraduate level), algorithms, and concrete models of computation, by Jeff Erickson
- Algorithms (various), by Har-Peled
- Algorithmic aspects of computer networks, by John Byers
- Algorithms and linear programming and algorithms and their analysis, by Uriel Feige
- Advanced algorithms and randomized algorithms, by Eric Vigoda
- Advanced algorithms (notes), by Johan Hastad
- Introduction to algorithms, by David Mount
- Advanced algorithms, by Jon Kleinberg
- Approximation and network algorithms, by Eva Tardos
- Algorithms in molecular biology, by Martin Tompa
- Approximability of optimization problems (and PCP), by Madhu Sudan
- Algorithmic problems in communication networks and algorithms in packet networks, by Adi Rosen
- Advanced data structures, by Erik Demaine
- Distributed algorithms: Fall 2002 and Fall 2001, by Nancy Lynch
- Game theory
- Misc theory (incl. quantum computation)
- Data Privacy, by Smith and Slavkovic
- Spectral graph theory, and Graphs and Networks, by Spielman
- Courses by Jon Kleinberg
- Quantum algorithms and complexity, by Ambainis
- Introduction to quantum information processing, by Mosca et al.
- Topics in quantum information, by Nayak
- (see here for a list of available courses)
- Quantum error correction, by Gottesman
- Quantum computing, by Dave Bacon
- Lower bounds in CS, by Amit Chakrabarti
- Lattices in CS, by Regev
- Spectral graph theory, by Spielman
- Metric embeddings, by Gupta and Ravi
- Advanced learning theory, by Rocco Servedio
- Machine learning theory, by Avrim Blum
- Machine learning, by Adam Klivans
- Learning theory, by Ron Rivest
- Algebra and computation (see also here), by Madhu Sudan
- Algebraic methods in combinatorics and computer science (mostly links to other stuff), by Amir Shpilka
- Quantum computation, by Jaikumar Radhakrishnan
- Quantum computation, by John Watrous (see here for links to other quantum notes)
- Quantum computing: Fall '97, Fall 2000,
Fall 2002, and Fall 2008, all by Umesh Vazirani (see also his list of courses)
- Quantum computation, by John Preskill
- Quantum mechanics (for computer scientists), by David Mermin
- Quantum computation, circuit complexity, and communication complexity, by Ran Raz
- *Quantum information processing and advanced algorithms, by Dieter van Melkebeek
- TCS Internet research problems, by Tom Leighton, Bruce Maggs, Ravi Sundaram, and Shan-Hua Teng
- Quantum computation, by Mario Szegedy
- Quantum computation, by Dorit Aharonov
- Combinatorics and graph theory, by David Zuckerman
- Boolean circuit complexity and concrete complexity, by Uri Zwick
- "A theorist's toolkit", by Sanjeev Arora
- Markov chain Monte Carlo methods, by Eric Vigoda
- Computational geometry, by David Mount
- Message routing in parallel machines, by Martin Tompa
- Applied extremal combinatorics: 1998 and 1996, by Dan Spielman
- Math