CSE 203A - Advanced Algorithms
Syllabus
- Randomized algorithms
- Approximation algorithms
- Checking matrix multiplication and polynomial identity testing
- Min-cut, 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 twenty-eighth annual ACM symposium on Theory of computing, pages 20-29, 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, 1115-1145, 1995.
|
|