E0 234: Introduction to Randomized Algorithms, Spring 2023

Instructors: Arindam Khan and Jaikumar Radhakrishnan

TA: Aditya Subramanian

Time: Mondays & Wednesdays, 14:00-15: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.
  


• Lectures 1-4 [Jan 4-16]: 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.


• Lectures 5-6 [Jan 18-23]: Moments and Deviation: Markov's and Chebyshev's inequality, power of sampling: a randomized algorithm for computing the median, minimum weight spanning tree (Karger-Klein-Tarjan). [M-U Chapter 3].
  Notes.
  Related Links:
  Quicksort concentration: by McDiarmid-Hayward.
  MWST algorithm by Karger-Klein-Tarjan.


• Lectures 7-8 [Jan 25-30]: Concentration inequalities (Chernoff), application. [M-U Chapter 4]


• Lectures 9-12 [Feb 1-13]: Balls and bins, birthday paradox, Poisson distribution, hashing, random graphs, threshold behavior in random graphs. [M-U Chapter 5]


• Lectures 13-14 [Feb 15-20]: Lovasz local lemma and Moser-Tardos algorithm.


• Lectures 15-18 [Feb 22-Mar 6]: Markov chains and random walks: algorithms for 2-SAT, 3-SAT, s-t connectivity. Monte Carlo methods, Markov Chain Monte Carlo, Metropolis algorithm, DNF counting, coupling. [M-U Chapter 7, 11, 12]


• Lectures 19-22 [Mar 8-20]: Introduction to algebra and probability: primality testing, verifying matrix multiplication, polynomial identity testing, randomized communication complexity, frequency moments in streams.


• Lectures 23-24 [Mar 27-29]: VC dimensions, epsilon net, epsilon sample, PAC, and agnostic learning. [M-U Chapter 14 and SH-UIUC Chapter 20]


• Lectures 25-26 [Apr 3-5]: Randomization and data structures.


• Lectures 27-28 [Apr 10-12]: Randomization in geometric algorithms.
  Related Links: Agarwal-Sen Survey, Cheong-Mulmuley-Ramos Survey.



Important Dates:
Course Drop Deadline without mention: March 2, 2023.
Course Drop Deadline with mention: April 1, 2023.
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, 2021 , by Siddharth Barman and Arindam Khan. (Previous offering)
• 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. Color Coding
• Color Coding, by Alon, Yuster, Zwick.
• Mixing Color Coding-Related Techniques Meirav Zehavi.


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


9. Sketching
• Survey by David Woodruff.


10. PCP
• Survey by Radhakrishnan and Sudan.


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


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


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


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


15. Perfect Sampling of k-Colorings
• Improved Bounds for Perfect Sampling of k-Colorings in Graphs, Bhandari-Chakraborty [Best Student Paper in STOC 2020].


16. 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.


17. 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.


18. 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.


19. 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.


20. 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.



---

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

---