Office hours: Wed 3-4pm, CSE 640
Office hours: Thurs 12-1pm, 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.
|28-Sep||Some basics||Schwartz-Zippel Lemma|
|3-Oct||Linearity of expectation||Incidence geometry and sum-product estimates|
|5-Oct||Second moments||Sinclair's lecture on random k-SAT: Lec 1, Lec 2|
|10-Oct||More on second moments||See Chapter 5 of Lyons-Peres,
Cover time of the discrete torus
|12-Oct||Chernoff bounds and randomized rounding||Concentration inequalities: A non-asymptotic theory of independence|
|17-Oct||Routing in the hypercube|
|19-Oct||NO CLASS (affiliates)|
|24-Oct||Martingales and Azuma's inequality|
|26-Oct||More martingales, chromatic number|
|31-Oct||Random tree embeddings|
|2-Nov||Bourgain's embedding||Matousek's lecture notes on metric embeddings|
|9-Nov||Compressive sensing||The Effectiveness of Convex Programming in the Information and Physical Sciences (youtube)|
|14-Nov||Random walks and electrical networks||Doyle & Snell's book on this topic|
|21-Nov||Markov chains and mixing times|
|28-Nov||Bubeck: Stochastic gradient descent|
|30-Nov||Bubeck: Stochastic gradient II (starts 10 minutes late at 1:40pm!)|
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 high-fidelity 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 high-dimensional 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:30-2:50
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.