Lecture Notes

This page provides quick links to lecture notes that I have written for various classes:

• CS254: A graduate class on computational complexity (Stanford)
  [Spring 2010 Class Home Page]
  [Notes for Lectures 1-8]

• CS278: A graduate class on computational complexity (Berkeley)
  [Spring 2001 Class Home Page]
  [Fall 2002 Class Home Page]
  [2001 Lecture Notes in book form]
  [2002 Lecture Notes in book form]

• CS276: A graduate class on the foundations of cryptography

  [Spring 2009 Class Home Page]
  [Lecture Notes as blog posts]
  [Lecture notes collected in book form]

• CS261: An introductory graduate class on exact and approximate algorithms for combinatorial optimization problems

  [Winter 2011 Class home page]
  [Lecture notes as blog posts]
  [Lecture notes collected in book form]

Topics classes:

• Graph Partitioning and Expanders
  [Lecture Notes]
  [2011 Class Home Page]

• PCP and Hardness of Approximation
  [2006 Class Home Page]

• Pseudorandomness and Combinatorial Constructions
  [2005 Class Home Page]

• Applications of Coding Theory to Computational Complexity
  [2003 Class Home Page]