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

1. Probability and Computing by Mitzenmacher and Upfal
2. Approximation algorithms by Shmoys and Williamson

Supplementary Reading

1. 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
2. Robin Moser, A Constructive Proof of the Lovasz Local Lemma, STOC '09 Proceedings of the 41st ACM symposium on Theory of computing, 2009.
3. 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.