Office hours: Wed 34pm, CSE 640
Office hours: Thurs 121pm, CSE 021
Class email list: cse525a_au16@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 
28Sep  Some basics  SchwartzZippel Lemma  
3Oct  Linearity of expectation  Incidence geometry and sumproduct estimates  
5Oct  Second moments  Sinclair's lecture on random kSAT: Lec 1, Lec 2  
10Oct  More on second moments  See Chapter 5 of LyonsPeres,
Cover time of the discrete torus 

12Oct  Chernoff bounds and randomized rounding  Concentration inequalities: A nonasymptotic theory of independence  
17Oct  Routing in the hypercube  
19Oct  NO CLASS (affiliates)  
24Oct  Martingales and Azuma's inequality  
26Oct  More martingales, chromatic number  
31Oct  Random tree embeddings  
2Nov  Bourgain's embedding  Matousek's lecture notes on metric embeddings  
7Nov  Dimension reduction  
9Nov  Compressive sensing  The Effectiveness of Convex Programming in the Information and Physical Sciences (youtube)  
14Nov  Random walks and electrical networks  Doyle & Snell's book on this topic  
16Nov  Cover times  
21Nov  Markov chains and mixing times  
23Nov  
28Nov  Bubeck: Stochastic gradient descent  
30Nov  Bubeck: Stochastic gradient II (starts 10 minutes late at 1:40pm!)  
5Dec  
7Dec 
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:
Mon & Wed, 1:302:50
CSE 403
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 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.
Exams:
Useful books: