CSE590RA: Randomized Algorithms

• Meeting Time: Monday, 3:30 -- 4:30pm
• Meeting Place: Sieg 422, except for Monday, January 25 when we will meet in EE1 045
• Mailing List: cse590ra@cs.washington.edu

Tentative Plan for Seminar

Papers

• http://theory.lcs.mit.edu/~karger/papers.html
• http://www.research.att.com/~edith/publications.html

1. D. Karger, Randomization in graph optimization problems, a survey.
2. D. Karger, A randomized fully polynomial approximation scheme for the all terminal network reliability problem.
3. D. Karger, Random sampling in cut, flow and network design problems.
4. D. Karger, Using random sampling to find maximum flows in uncapacitated undirected graphs.
5. D. Karger, Better random sampling algorithms for flows in undirected graphs.
6. D. Karger and M. Levine, Finding maximum flows in undirected graphs seems easier than bipartite matching.
7. D. Karger, Random sampling and greedy sparsification for matroid optimization problems.
8. E. Cohen, Size-estimation framework with applications to transitive closure and reachability

For more information, contact Anna Karlin (karlin@cs.washington.edu)