E0 234: Introduction to Randomized Algorithms, Spring 2025

Instructors: Arindam Khan and Anand Louis

TA: KVN Sreenivas and Arka Ray

Time: Mondays & Wednesdays (& Fridays), 11:00-12:30, CSA112.

Course Description

Tentative topics: Basics of probability, Monte Carlo and Las Vegas algorithms, Karger's min-cut Algorithm, coupon collector, quicksort. Moments and deviation: Markov's and Chebyshev's inequality, power of sampling: a randomized algorithm for computing the median. Concentration inequalities (Chernoff bounds), application. Balls and bins, birthday paradox, Poisson distribution, hashing, random graphs, threshold behavior in random graphs. Lovasz local lemma and Moser-Tardos algorithm. Introduction to algebra and probability: primality testing, verifying matrix multiplication, polynomial identity testing, randomized communication complexity, frequency moments in streams. Markov chains, random walks. Monte Carlo methods, coupling. VC dimensions, epsilon net, epsilon sample, PAC, and agnostic learning. Randomized data structures, randomized geometric algorithms.

---

Lectures

• Probability Refresher: Scribe notes from Toolkit, Handwritten notes.
  Useful inequalities: Cheatsheet.
  
• History of Probability and Randomness:
  A History of the Mathematical Theory of Probability: From the Time of Pascal to that of Laplace,
  Probability in Ancient India,
  The Empire of Chance ,
  Taming of Chance,
  The Emergence of Probability,
  


• Lectures 1-4 [Jan 8-15]: Basics, Karger's min-cut algorithm, coupon collector, quicksort, complexity classes, Monte Carlo, and Las Vegas algorithms. [M-U Chapter 1, 2]
  Notes.
  References:
  Backward analysis of quicksort: Miller's notes, Har-Peled's notes.
  Randomized Complexity Classes: [Arora-Barak].
  Related Links:
  Linearity of expectations: Notes by Yufei Zhao.
  Monty Hall Problem: Monograph by Gill.
  Birthday Paradox: Review by Dasgupta.
  Different Discrete Distributions: Notes from UConn.
  Probabilistic analysis of algorithms: Survey by Bentley and Lueker.
  Min cut papers: (Randomized) Karger [SODA'93], Karger-Stein [JACM'96], Karger [JACM'00].
  Min cut papers: (Deterministic) Stoer and Wagner [JACM'97], Li [STOC'21].
  Max flow/ s-t cut problem: Max flow and min-cost flow in almost linear time: Chen et al. [Best paper in FOCS'22], Quanta Article,
  Gomory-Hu trees in nearly quadratic time: Abboud et al. [FOCS'22], Debmalya Panigrahi's talk at IISc on Ramanujan Day,
  k-cut problem: Gupta et al. [STOC'19], Anupam Gupta's talk on k-cut.
  Quicksort: Variants and improvements [by Martinez].
  On tail estimates for Randomized Incremental Construction: By Sandeep Sen.
  Backwards analysis: Monograph by Siedel, Analysis of MWST (Karger-Klein-Tarjan) by Timothy Chan.




Important Dates:
Final: Late April (TBA).

---

References

We will be teaching materials from multiple books/sources. Some of them are the following.
• [M-U] Michael Mitzenmacher and Eli Upfal. Probability and computing. Cambridge university press, 2017.
• [MR] Rajeev Motwani, Prabhakar Raghavan. Randomized Algorithms, Cambridge university press.
• [RK] R.M. Karp, An introduction to randomized algorithms, Discrete Applied Mathematics, 34, pp. 165-201, 1991.
• [BHK] Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of Data Science, 2020.
• [RV] Roman Vershynin, High-Dimensional Probability.
• [DP] D.B. Dubhashi, A. Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms, Cambridge University Press, 2009.
• [LPW] David A. Levin, Yuval Peres, Elizabeth L. Wilmer. Markov Chains and Mixing Times.
• [MIT-YZ] Yufei Zhao. Lecture Notes (The Probabilistic Methods in Combinatorics), MIT, 2020.
• [A-S] Noga Alon and Joel Spencer, The probabilistic method, John Wiley & Sons, 2004.
• [UW-TR] Thomas Rothvoss, Lecture Notes (Probabilistic Combinatorics), U Washington, 2019.
• [AC] Amit Chakrabarti, Data Stream Algorithms, 2020.
• [SM] S. Muthukrishnan. Data streams: Algorithms and applications. Now Publishers Inc, 2005.
• Various surveys and lecture notes.

Similar courses elsewhere:
• IISc, 2023 , by Arindam Khan and Jaikumar Radhakrishnan. (Previous offering)
• IISc, 2021 , by Siddharth Barman and Arindam Khan.
• IISc, 2016 , by Arnab Bhattacharyya and Deeparnab Chakrabarty.
• Yale, 2020 , by James Aspnes.
• [SH-UIUC] UIUC, 2018 , by Sariel Har-Peled.
• MIT, 2002 , by David Karger.
• UT Austin, 2020 , by Eric Price.
• UC berkeley, 2003 , by Luca Trevisan.
• Columbia, 2019 , by Tim Roughgarden.
• Stanford, 2020 , by Mary Wooters.
• Wiezmann, 2013 , by Robert Krauthgamer and Moni Naor.
• UMCP, 2017 , by Aravind Srinivasan.
• U Iowa, 2018 , by Sriram V. Pemmaraju.
• UBC, 2012 , by Nick Harvey.
• EPFL 2014 , by Friedrich Eisenbrand.
• NUS, 2019 , by Seth Gilbert.
• Duke, 2013 , by Kamesh Munagala.
• NTHU, 2012 , by Wing Kai Hon.
• U Waterloo, 2019, by Gautam Kamath.
• U Waterloo, 2018 , by Lap Chi Lau.
• U Washington, 2016 , by James Lee.
• CMU, 1997 , by Avrim Blum.

Fun links:
• Drunkard's Walk, Book by Leonard Mlodinow.
• Veritasium Video, How We are Fooled By Probability: Regression to the Mean.
• Vsauce Video, Birthday Paradox.
• Numberphile Video, Monty Hall Problem.
• Sunlight is way older than you think, An interesting application of Random Walks (Markov chains).
• Veritasium Video, Bayes' theorem.
• MindYourDecisions Video, Buffon's Needle Problem: Pi from Probability.
• 3Blue1Brown Videos: Bayes' theorem, binomial distribution.



---

Assignments

• HW 1

---

Mathematical writing and LaTeX

• How to write mathematics (Halmos)
• Mathematical writing (Knuth et al.)
• Scribe template: preamble.tex, lect01.tex
• Overleaf: Learn LaTex
• MIT: Intro to LaTex
• Evan Chen's LaTex hacks
• TikZ package for drawing




---

Project Topics

For projects you need to select a project topic from the list given below. Some reference papers are given below. You are expected to do a survey of the results and techniques in the topic area. You can form a group of two students and send the project topic and group details by 20th February. You need to submit a report by the last_day_of_class. Finally, you need to make a presentation on the topic on the last week of classes.


1. Derandomization
• Notes by Salil Vadhan.
• Notes by Santosh Vempala.


2. Pairwise Independence
• Notes by Luby-Wigderson.


3. Dynamic algorithms for Matching
• Sublinear Time Algorithms and Complexity of Approximate Maximum Matching, by Behnezadm Roghani, Rubenstein..
• Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time, by Bhattacharyya, Kiss, Saranurak, Wajc.


4. Streaming Algorithms
• The space complexity of approximating the frequency moments, by Alon-Matias-Szegedy.
• On the Exact Space Complexity of Sketching and Streaming Small Norms, by Kane-Nelson-Woodruff.


5. Load Balancing
• How Asymmetry Helps Load Balancing, by Vocking.
• Power of 2 choices in graphical scheduling.


6. Balanced Allocation
• Balanced Allocation in Dynamic Setting.
• Balanced Allocations - Caching, Packing, Twinning.
• Dynamic load balancing.


7. Sublinear time algorithms
• Ronitt Rubinfeld's page.
• Goldreich Book.


8. Sketching
• Survey by David Woodruff.


9. PCP
• Survey by Radhakrishnan and Sudan.


10. Counting knapsack solutions
• Approximate Counting by Dynamic Programming.
• A faster fptas for# knapsack.


11. Discrepancy Minimization
• Lovett-Meka.
• Alweiss, Liu, Sawhney.


12. Expanders
• Survey by Hoori, Linial, Wigderson.


13. Minimax Theorem
• Ben-David,Blais [FOCS'20].


14. Singular Value Decompostion (SVD)
• Vempala, Santosh, and Grant Wang. "A spectral algorithm for learning mixtures of distributions." IEEE FOCS 2002.
• The paper shows that a simple spectral algorithm learns mixtures of Gaussians with provable guarantees, and extends the results the mixtures of weakly isotropic distributions.


15. Anti-concentration
• Lovett, Shachar. "An elementary proof of anti-concentration of polynomials in Gaussian variables." Electronic Colloquium on Computational Complexity (ECCC). Vol. 17. 2010.
• This gives us an elementary proof of anti-concentration for multilinear polynomials for a large class of distributions, which includes polynomials over Gaussian distributions.


16. Nearest Neighbor via LSH and p-Stable distributions
• Indyk, P., Motwani, R., Raghavan, P., & Vempala, S. Locality-preserving hashing in multidimensional spaces. STOC 1997.
• This paper introduces locality preserving hashing which has several applications in geometric optimization problems in high dimensions. It gives explicit constructions and lower bounds for these hash families.


17. Optimality of JL Lemma
• Larsen, Kasper Green, and Jelani Nelson. "Optimality of the Johnson-Lindenstrauss lemma." IEEE FOCS 2017.
• This paper shows bounds on dimensions that are necessary for any approximate isometry preserving maps.


18. PIT
• Primality and Identity Testing via Chinese Remaindering, by Manindra Agrawal and Somenath Biswas.
• Randomness Efficient Identity Testing of Multivariate Polynomials, by Adam Klivans and Daniel Spielman.


19. Applications of high-dimensional random walks
• Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid, by Anari et al.
• Log-Concave Polynomials IV: Approximate Exchange, Tight Mixing Times, and Near-Optimal Sampling of Forests, by Anari et al.


20. KLS conjecture
• An Almost Constant Lower Bound of the Isoperimetric Coefficient in the KLS Conjecture, by Chen.


21. Geometric random walks
• Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms, by Jia et al.


22. Localization Schemes
• Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains, by Chen and Eldan.



---

Intended audience: Graduate students in computer science and mathematics with theoretical interests. Interested undergraduate students with very strong mathematical skills.

Prerequisites: Mathematical maturity and a solid background in math (elementary combinatorics, graph theory, discrete probability, algebra, calculus) and theoretical computer science (big-O/Omega/Theta, P/NP, basic fundamental algorithms).

Grading: 40% HW, 30% Projects, 30% Final.

---

Prepared and Maintained by Arindam Khan

---