CS6170 Randomized Algorithms

July - Nov 2021

Topics/References for course reading

Below are a list of topics and related references. You can form groups of size at most 3 to read the material, and give a lecture in class during the normal lecture slot. We will schedule these towards the end of the semester. If you want to read some other topic of your choice, please talk to me about it.

Randomized rounding

  1. Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs - Raghavan and Thompson.
  2. Approximation Algorithms via Randomized Rounding: A Survey - Srinivasan.

Pessimistic estimators and derandomization

  1. Probabilistic Construction of Deterministic Algorithms - Approximating Packing Integer Programs - Raghavan.
  2. Derandomizing the Ahlswede-Winter Matrix-valued Chernoff bound using pessimistic estimators, and applications - Wigderson and Xiao.

Hashing

  1. The Power of Simple Tabulation Hashing - Patrascu and Thorup.
  2. Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream - Mitzenmacher and Vadhan.

Random walks and clustering

  1. A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning - Spielman and Teng.

This is the first of three papers (the others are here and here), that give a nearly linear-time algorithm for solving certain systems of linear equations. We will stick to just this paper.

Algebraic techniques

  1. Probabilistic Polynomials and Hamming Nearest Neighbors - Alman and Williams.
  2. An Illuminating Algorithm for the Light Bulb Problem - Alman.

Dimension reduction and applications

  1. Database-friendly random projections: Johnson-Lindenstrauss with binary coins - Achlioptas.
  2. Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality - Har-Peled, Indyk and Motwani.

Matching in graphs

  1. Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs - Goel, Kapralov and Khanna.
  2. Perfect Matchings in \(O(n \log n)\) Time in Regular Bipartite Graphs - Goel, Kapralov and Khanna.

Color-coding and subset sum

  1. Color-Coding - Alon, Yuster and Zwick.
  2. A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum - Bringmann.

Dynamic algorithms

  1. Maintaining a Large Matching and a Small Vertex Cover - Onak and Rubinfeld.
  2. Fully dynamic maximal matching in \(O(\log n)\) update time - Baswana, Gupta and Sen.

Online algorithms

  1. Online Budgeted Matching in Random Input Models with applications to Adwords - Goel and Mehta.
  2. Online Stochastic Matching: Beating \(1 − \tfrac{1}{e}\) - Feldman, Mehta, Mirrokni and Muthukrishnan.