CSE 203A  Advanced Algorithms
Syllabus
 Randomized algorithms
 Approximation algorithms
 Checking matrix multiplication and polynomial identity testing
 Mincut, Karger's algorithm
 more later
Useful Books
 Probability and Computing by Mitzenmacher and Upfal
 Approximation algorithms by Shmoys and Williamson
Supplementary Reading
 N. Alon, Y. Matias, and M. Szegedy, The space complexity of approximating the frequency moments, STOC '96 Proceedings of the twentyeighth annual ACM symposium on Theory of computing, pages 2029, 1996
 Robin Moser, A Constructive Proof of the Lovasz Local Lemma,
STOC '09 Proceedings of the 41st ACM symposium on Theory of computing, 2009.
 Michel Goemans and David Williamson, Improved Approximation Algorithms for
Maximum Cut and Satisfiability Problems Using Semidefinite Programming, Journal of the ACM, 1995, 11151145, 1995.
