E0 234: Introduction to Randomized Algorithms, Spring 2021
- Time: Tuesdays & Thursdays, 11:00 AM-12:30 PM, Online (Teams).
Basics of Probability, Monte Carlo and Las Vegas Algorithms, Karger's Min-cut Algorithm, Verifying Polynomial Identities.
Expectations, Coupon Collector, Quicksort, Moments and Deviation, Randomized Median Finding.
Chernoff Bounds, Balls, Bins, Random Graphs.
Markov Chains, Random Walks.
Monte Carlo Methods, Coupling.
Sample Complexity, VC Dimension.
Introduction to high-dimensional probability, Sub-Gaussian and Sub-Exponential distribution, Hoeffding's inequality, Bernstein's inequality.
Johnson-Lindenstrauss lemma, Lovasz Local Lemma and Probabilistic Methods.
Streaming Algorithms, Nearest Neighbor Search; Matrix Deviation Inequalities (MDI) and its Applications.
- Probability Refresher: Scribe notes from Toolkit,
- Week 1 (Arindam): Introduction, Monte Carlo and Las Vegas Algorithms, Karger's Min-cut Algorithm, Coupon Collector, Quicksort.
[M-U Chapter 1, 2]
Randomized Complexity Classes (Arora-Barak),
STOC'21 deterministic mincut paper,
Anupam Gupta's talk on k-cut.
- Week 2 (Arindam): Polynomial Identity Testing, Schwartz-Zippel Lemma, Isolation Lemma, MVV Perfect Matching Algorithm.
[M-U Chapter 1, and Notes]
Field version of Schwarz-Zippel,
Ola Svensson's talk on matching in Quasi-NC.
- Week 3 (Arindam): Concentration Inequalities, Randomized Median Selection, Set Balancing, Balls and Bins.
[M-U Chapter 3, 4, 5]
Hashing, Load Balancing and Multiple Choice - an excellent source for Balls and Bins related results,
Chazelle's book on Discrepancy Methods,
Concentration Inequality survey by McDiarmid.
- Week 4 (Arindam): Markov Chains; Random Walks; Algorithms for 2-SAT, 3-SAT, s-t connectivity.
[M-U Chapter 11, JA-YALE, LPW]
Derandomization of Schoning and k-SAT version,
ETH and SETH.
- Week 5 (Arindam): Monte Carlo Methods, Markov Chain Monte Carlo, Metropolis Algorithm, DNF Counting, Coupling..
[M-U Chapter 12, 13, JA-YALE, LPW]
- Week 6 (Arindam): VC Dimensions, Shattering dimension, Epsilon Net, Epsilon Sample, PAC and agnostic Learning.
[M-U Chapter 14 and SH-UIUC Chapter 20]
Set covers in finite VC-dimension,
Epsilon-Nets and Simplex Range Queries.
- Week 7 (Siddharth): Introduction to high-dimensional probability, Sub-Gaussian and
Sub-Exponential distribution, Hoeffding's inequality, Bernstein's inequality.
[RV Chapter 2]
- Week 8 (Siddharth): Sub-Gaussian random vectors, Concentration of the norm, Johnson-Lindenstrauss Lemma (JL).
[RV Chapter 2 and Notes]
Sparse JL [Achlipotas 03],
Fast JL [Ailon Chazelle 09].
- Week 9 (Siddharth): JL Applications: Streaming Algorithms (AMS F2 estimation),
Nearest Neighbor Search; Matrix Deviation Inequalities (MDI), Gaussian width, MDI tail inequality.
[RV Chapter 4,7,9 and Notes]
- Week 10 (Siddharth): MDI Applications: Spectra of random matrices, covariance estimation,
random projection of sets, random sections of sets (M* bounds), Escape Theorem (Gordan), compressed sensing.
[RV Chapter 4,5,7,9,10 and Notes]
- Week 11 (Siddharth): MDI Applications: Community Detection, Spectral Clustering. Lovasz Local Lemma.
LLL Notes from Toolkits'20: Handwritten, Scribe..
Course drop deadline without mention: 26 April, 2021.
Course drop deadline with mention: 26 May, 2021.
Project presentations: 25th and 27th May, 2021.
Project report submission deadline: 27th May, 2021.
Final: 5th June, 2021.
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, 2019.
- [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, 2016 , by Arnab Bhattacharyya and Deeparnab Chakrabarty.
- [JA-YALE] 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.
- CMU, 1997 , by Avrim Blum.
- 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.
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 April.
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 (May 25 and May 27).
Sublinear time algorithms
Streaming Algorithms for Coin Tossing
Random Order Arrival (Online Algorithms)
Stochastic analysis of bin packing
Counting knapsack solutions
Solving sparse linear systems
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.
- Kumar, A., Sabharwal, Y., & Sen, S. "A simple linear time (1+ epsilon)-approximation algorithm for k-means clustering in any dimensions."" IEEE FOCS 2004.
- This paper gives the first linear time algorithm for k means, using random subsampling of point sets.
- 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.
Approximate Matrix Multiplication
- Drineas, P., Kannan, R. and Mahoney, M.W., 2006. Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication. SIAM Journal on Computing, 36(1), pp.132-157.
- This paper gives fast approximation algorithms for matrix multiplication via matrix sub-sampling, with several applications.
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.
Computing Gaussian Width
- Meka, R. A PTAS for computing the supremum of Gaussian processes. IEEE FOCS 2012.
- This gives a PTAS for computing the supremum of Gaussian processes.
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.
Intended audience: Graduate students in computer science
and mathematics with theoretical interests.
Interested undergraduate students with very strong mathematical
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