CS1.406 Advanced Algorithms (Spring 2024)
Announcements
- Teaching assistants: Nithish Raja, Vidit Jain
- Schedule: Tuesday and Friday, 14:00 – 15:30
- Classroom: H104
Topics
-
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].
-
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
-
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.
-
MaxSAT, MaxCUT, Derandomization with conditional probabilities
- Class notes
- References: Section 6.2 and 6.3 of [2].
-
Min-Cut, and Las Vegas & Monte carlo
- Class notes
- References: Sections 1.1 and 1.2 of [1] and Section 1.4 of [2].
-
Approximate Counting & Approximate Sampling
- Class notes
- References: Section 11.2 of [1] and Sections 10.1 and 10.2 of [2].
-
Random walks and Markov chains
- Class notes
- References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].
-
Markov Chains – 2SAT
- Class notes
- References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].
-
Markov Chains – 3SAT
- Class notes
- References: Sections 6.1, 6.2 and 6.3 of [1], and Section 7.1 of [2].
-
Concentration bounds
- Class notes
- References: Chapter 4 of [2].
-
Chernoff bound, Error reduction, Set balancing
- Class notes
- References: Chapter 4 of [2].
References
- R. Motwani and P. Raghavan (1995), Randomized Algorithms, Cambridge University Press.
- M. Mitzenmacher and E. Upfal (2005), Probability and Computing, Cambridge University Press.
- N. Alon and J. Spencer (2015), The Probabilistic Method, Wiley, USA.
Similar courses
- Previous offering of the course - Spring 2022
- See the course at IISc by Siddharth Barman & Arindam Khan (and a list of similar courses on that page).