Office hours: Thursday, 121:30pm in CSE 640 or by appointment
Office hours: Monday, 121pm in CSE 306 or by appointment
Class email list: cse525a_wi15@uw
Note that the "bonus material" is not required reading. It's there if you're interested in learning more about the topic of the lecture and its broader applications.
class  topic  notes  bonus material 
6Jan  some basics  SchwartzZippel Lemma  
8Jan  the probabilistic method, linearity of expectation  Incidence geometry and sumproduct estimates, Flows and eigenvalues  
13Jan  the second moment method  See Chapter 5 of LyonsPeres  
15Jan  a second helping of second moments  Cover time of the discrete torus  
20Jan  Chernoff bounds and randomized rounding  Concentration inequalities: A nonasymptotic theory of indepenence  
22Jan  the method of Laplace transforms  
27Jan  martingales and Azuma's inequality  
29Jan  '' ''  
3Feb  Bourgain's embedding  Matousek's lecture notes on metric embeddings  
5Feb  memoryless random variables and lowdiameter partitions  
10Feb  the curse of dimensionality and dimension reduction  
12Feb  compressive sensing and the RIP  The Effectiveness of Convex Programming in the Information and Physical Sciences (video)  
19Feb  concentration for sums of independent random matrices  Proof of GoldenThompson,
Trace inequalities and quantum entropy 

24Feb  '' ''  
26Feb  spectral sparsification via sampling  Twice Ramanujan sparsifiers  
3Mar  random walks: hitting times, commute times, and cover times  Random walks and electric networks (Doyle & Snell) 

5Mar  '' ''  
10Mar  Markov chains and mixing times  
12Mar  eigenvalues, expansion, and rapid mixing  Approximating the permanent 
Metaphysical. Randomness is a powerful and ubiquitous tool in algorithm design and data analysis. This is especially true in a world overrun by data. No efficient algorithm can possibly take a highfidelity view of all of it. But often we don't have to; uncertainty plays the dual roles of blessing and curse. And in our darkest highdimensional hour, "concentration of measure" allows us to extract information without first knowing where to look.
Sometimes the signal is everywhere. Sometimes we only need a glimpse of the truth to head in the right direction. Sometimes a random direction suffices.
Where & when:
Tues & Thurs, 10:3011:50
EEB 025 on 15Jan
EEB 037 afterward
Homeworks:
[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.]
Exams:
Useful books: