CS1.406 Advanced Algorithms (Spring 2024)

---

Announcements

• Teaching assistants: Nithish Raja, Vidit Jain
• Schedule: Tuesday and Friday, 14:00 – 15:30
• Classroom: H104

Topics

1. Introduction to Polynomial Identity Testing, Univariate Interpolation, Verifying Matrix Multiplication

   • Class notes
   • References: Section 7.2 & 7.3 of [1], and Section 1.1 & 1.3 of [2].

2. DeMillo-Lipton-Schwartz–Zippel lemma, The isolation lemma and Mulmuley, Vazirani, and Vazirani algorithm for matching

   • Class notes
   • References: Section 12.4 of [1], Section Moshkovitz’s alternate proof of DLSZ lemma, and Mulmuley-Vazirani-Vazirani ‘87

3. Randomized routing

   • Class notes
   • References: Section 4.2 of [1], Section 4.5.1 of [2], Lovett’s course notes from UCSD, and J R Lee’s course notes from UWash.

4. MaxSAT, MaxCUT, Derandomization with conditional probabilities

   • Class notes
   • References: Section 6.2 and 6.3 of [2].

5. Min-Cut, and Las Vegas & Monte carlo

   • Class notes
   • References: Sections 1.1 and 1.2 of [1] and Section 1.4 of [2].

6. Approximate Counting & Approximate Sampling

   • Class notes
   • References: Section 11.2 of [1] and Sections 10.1 and 10.2 of [2].

7. Random walks and Markov chains

   • Class notes
   • References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].

8. Markov Chains – 2SAT

   • Class notes
   • References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].

9. Markov Chains – 3SAT

   • Class notes
   • References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].

10. Concentration bounds

    • Class notes
    • References: Chapter 4 of [2].

11. Chernoff bound, Error reduction, Set balancing

    • Class notes
    • References: Chapter 4 of [2].

References

1. R. Motwani and P. Raghavan (1995), Randomized Algorithms, Cambridge University Press.
2. M. Mitzenmacher and E. Upfal (2005), Probability and Computing, Cambridge University Press.
3. N. Alon and J. Spencer (2015), The Probabilistic Method, Wiley, USA.

Similar courses

1. Previous offering of the course - Spring 2022
2. See the course at IISc by Siddharth Barman & Arindam Khan (and a list of similar courses on that page).