Office: TAY 3.134
Office Hours: TTh 2-3, or by appointment.
Office: 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.
P. Indyk's survey Algorithmic Aspects of Geometric Embeddings
S. Dasgupta and 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
D. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs (online book)
My Pseudorandomness Lecture Notes (Lectures 11, 12, and 16 cover expanders, eigenvalues, mixing times, and cover times of random walks)
S. Hoory, N. Linial, and A. Wigderson's survey Expander Graphs and Their Applications
N. Nisan and A. Wigderson, Hardness vs. Randomness
Problem Set #1
Problem Set #2 Solutions
Problem Set #3 Solutions
Problem Set #4 Solutions
Problem Set #5 Solutions
Problem Set #6 Solutions
Problem Set #7 Solutions
Problem Set #8 Solutions
2006 Midterm Solutions
The final exam will be cumulative and held on Friday, December 12, from 9am - noon in the regular classroom. No make-up exams will be given, so please plan accordingly. For the midterm, you may bring a single, 8.5x11 inch, handwritten sheet of paper, with writing on both sides; for the final you may bring two such sheets. No calculators are allowed (they won't be necessary).