Office hours: Tues, 34pm, CSE 640
Tue, Apr 02
First moments 

Thu, Apr 04
Second moments 

Tue, Apr 09
More second moments 

Thu, Apr 11
Chernoff bounds 

Tue, Apr 16
Applications of Chernoff bounds 

Thu, Apr 18
Martingales and Azuma's inequality 

Tue, Apr 23
Applications of martingales 

Thu, Apr 25
Random tree embeddings 

Tue, Apr 30
Bourgain's embedding 

Thu, May 02
Dimensionality reduction 

Tue, May 07
Compressive sensing 

Thu, May 09
Sums of independent random matrices 

Tue, May 14
Spectral sparsification 

Thu, May 16
Random walks and electrical networks 

Tue, May 21
Hitting times and cover times 

Thu, May 23
Markov chains and mixing times 

Tue, May 28
Markov chains and mixing times (cont.) 

Thu, May 30
Eigenvalues, expansion, and rapid mixing 

Tue, Jun 04
NO CLASS [final exam] 

Thu, Jun 06
NO CLASS [final exam] 
You may discuss problems with your classmates, but when you write down the solutions, you should do so by yourself. You can use the internet and books for reference material but you must cite every source that you consulted (the name of the book or web page suffices). You should also cite any classmates with whom you discussed solutions.
All homework should be turned in electronically to the Dropbox by the due date for the assignment. Homework should either be typeset (greatly preferred) or written very neatly and scanned.
Late HW policy: I will allow one (slightly) late homework per person (e.g., to accomodate for a paper deadline). This must be arranged beforehand.
Note on Bonus problems: These problems are usually quite challenging. If you do some of them, I will be impressed. But they are in no way required (or even suggested) for obtaining a good grade in the course.