Office: TAY 3.134
Office Hours: W 2-3 and F 3-4, or by appointment.
Office (for office hours): ESB 229
Office (for all other purposes): TAY 3.108
Office Hours: M 3-4
Review Sheet from my
Combinatorics and Graph Theory course.
Errata for the text. Doesn't include error in Problem 7.3.
S. Dasgupta, A. Gupta, An Elementary Proof of a Theorem of Johnson and Lindenstrauss
D. Achlioptas, Database-friendly Random Projections: Johnson-Lindenstrauss with Binary Coins
M. Goemans, Lecture Notes on Linear Programming
M. Goemans and D. Williamson, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming
My Pseudorandomness Lecture Notes
N. Nisan and A. Wigderson, Hardness vs. Randomness
Problem Set #1
Problem Set #2
Problem Set #3
Problem Set #4
Problem Set #5
Problem Set #6
Problem Set #7
Problem Set #8
The final exam will be cumulative and held on Thursday, December 14, from 2-5pm in ETC 2.132. You may bring two 8.5x11 inch, handwritten sheets of paper, with writing on both sides. No calculators are allowed (they won't be necessary).