CPSC 536N: Randomized Algorithms

General Information

Course Website: http://www.cs.ubc.ca/~nickhar/W12

Lecture Time: Tuesdays & Thursdays, 9:30am-11:00am

Lecture Room: DMP 101

Instructor: Prof. Nicholas Harvey, X851, nickhar@cs.ubc.ca

 

Course Blog

 

Syllabus

 

Project

·         Proposal Due Tuesday February 28th, in class.

 

Assignments

·         Assignment 1: Due Thursday February 2nd, in class.

·         Assignment 2: Due Thursday March 1st, in class.

·         Assignment 3: Due Tuesday April 3rd, in class.

 

Lectures
Updated lecture notes can be found in my 2015 offering of this class.

 

Date

Topics

Reading in Textbooks

Notes

1

1/5

Overview, Equality Testing, Max Cut

MU 1.2, 2.1-2.4

PDF, Blog

2

1/10

Markov’s Inequality, Amplification by Independent Trials, Chernoff Bound

MU 3.1, 4.1-4.2, MR 3.2, 4.1

PDF, Blog

3

1/12

Balls and Bins, Congestion Minimization, Negative Binomial Distribution

MU 5.2, MR 4.3

PDF, Blog

4

1/17

Quicksort, SkipNet

DP 2.4

PDF, Blog

5

1/19

SkipNet Analysis, Consistent Hashing

PDF, Blog

6

1/24

Dimensionality Reduction by the Johnson-Lindenstrauss Lemma

DP 2.5

PDF, Blog

7

1/26

Streaming Algorithms, Nearest Neighbor

PDF, Blog

8

1/31

Compressed Sensing

PDF, Blog

9

2/2

Polynomial Identity Testing by the Schwartz-Zippel Lemma

MR 7.2

PDF, Blog

10

2/7

Minimum Cuts by the Contraction Algorithm

MU 1.4, MR 1.1 & 10.2

PDF, Blog

11

2/9

Graph Sparsifiers

PDF, Blog

12

2/14

Concentration for Sums of Random Matrices

PDF, Blog

13

2/16

The Ahlswede-Winter Inequality

PDF, Blog

14

2/28

Spectral Sparsifiers

PDF, Blog

15

3/1

Low-rank Approximation of Matrices

PDF, Blog

16

3/6

Derandomization: Method of Conditional Expectations, Method of Pessimistic Estimators

MU 6.3, MR 5.6

PDF, Blog

17

3/8

Chebyshev’s Inequality, Pairwise Independence

MU 3.2-3.3, 13.1-13.2, MR 3.2 & 3.4

PDF, Blog

18

3/13

Perfect Hashing

MU 13.3

PDF, Blog

19

3/15

The Lovasz Local Lemma

MU 6.7, MR 5.5, AS 5

PDF, Blog

20

3/20

Expanders, Superconcentrators

MR 6.7

PDF, Blog

21

3/22

Property Testing

PDF, Blog

22

3/27

Random Partitions of Metric Spaces

PDF, Blog

23

3/29

Random Partitions of Metric Spaces, Continued

PDF, Blog

24

4/3

Probabilistic Approximation of Metrics by Trees

PDF, Blog

25

4/5

Online Steiner Tree

PDF, Blog

 

Further Reading

Review of Discrete Probability

E. Lehman, F. T. Leighton and A. Meyer. Mathematics for Computer Science. Ch 14-18.

 

Chernoff Bound

E. Lehman, F. T. Leighton and A. Meyer. Mathematics for Computer Science. Ch 19.

C. McDiarmid. Concentration. Sections 1 & 2.

T. Tao. ­254A Lecture Notes 1: Concentration of Measure.

 

Notes on Convexity Inequalities

 

Congestion Minimization

D. Williamson and D. Shmoys. The Design of Approximation Algorithms. Section 5.11.

 

Consistent Hashing

D. Lewin. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web.

D. Karger, E. Lehman, F. T. Leighton, M. Levine, D. Lewin and R. Panigrahi. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. STOC 1997.

 

Dimensionality Reduction by Johnson-Lindenstrauss

M. Goemans. Metric Embeddings. Lecture 6.

A. Gupta and R. Ravi. Algorithmic Applications of Metric Embeddings. Lecture 15.

 

Data Streams

P. Indyk. Sketching, Streaming, and Sub-linear Space Algorithms. Lecture 2.

S. Muthukrishnan. Data streams: algorithms and applications.

 

Nearest Neighbor

P. Agarwal. Geometric Optimization. Lecture 25.

P. Indyk and R. Motwani. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. STOC 1998.

A. Andoni and P. Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions.

 

Compressed Sensing

P. Indyk. Sketching, Streaming, and Sub-linear Space Algorithms. Lecture 5 and Lecture 5 Slides.

R. Baraniuk, M. Davenport, R. DeVore, M. Wakin. A simple proof of the restricted isometry property for random matrices.

E. Candes, J. Romberg, T. Tao. Stable signal recovery from incomplete and inaccurate measurements.

 

Schwartz-Zippel & Polynomial Identity Testing

R. Lipton. The Curious History of the Schwartz-Zippel Lemma. Blog post from Gödel's Lost Letter and P=NP.

V. Kabanets. Pseudorandomness. Lecture 2.

 

Minimum Cuts

D. Karger. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. SODA 1993.

D. Karger. Random Sampling in Cut, Flow and Network Design Problems, Appendix A. STOC 1994.

 

Graph Sparsifiers

A. Benczur and D. Karger. Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs. STOC 1996.

W. Fung and N. Harvey. Graph Sparsification by Edge-Connectivity and Random Spanning Trees. STOC 2011.

R. Hariharan and D. Panigrahi. A General Framework for Graph Sparsification. STOC 2011.

 

Notes on Symmetric Matrices

 

Concentration for sums of random matrices

R. Ahlswede and A. Winter. Strong converse for identification via quantum channels. Appendix.

A. Wigderson and D. Xiao. Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications. Section 2.

 

Spectral Sparsifiers

D. Spielman and N. Srivastava. Graph Sparsification by Effective Resistances. STOC 2008.

 

Low-rank approximation of matrices

M. Mahoney. Randomized algorithms for matrices and data.

N. Halko, P. G. Martinsson, J. A. Tropp. Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions.

 

Pessimistic Estimators

A. Srinivasan. Randomized Algorithms. Handout 5.

N. Young. Greedy Algorithms Blog. Method of Conditional Probabilities, Pessimistic Estimators, and Pessimistic Estimators for Chernoff Bounds.

P. Raghavan. Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs.

 

Universal Hash Families

M. Luby and A. Wigderson. Pairwise Independence and Derandomization.

 

Lovasz Local Lemma

L. Fortnow. A Kolmogorov Complexity Proof of the Lovász Local Lemma. Blog post from Computational Complexity.

T. Tao. Moser’s entropy compression argument. Blog post from What’s new.

R. Moser and G. Tardos. A constructive proof of the general Lovasz Local Lemma. JACM 2010.

 

Expanders

S. Hoory, N. Linial and A. Wigderson. Expander Graphs and Their Applications. Chapter 1.

 

Property Testing

L. Lau. Randomness & Computation. Lecture 10: Sublinear algorithms.

R. Rubinfeld. Sublinear time Algorithms.

D. Ron. Algorithmic and Analysis Techniques in Property Testing.

 

Random Partitions of Metric Spaces

J. Lee. Random Partitions of Metric Spaces. Blog post from tcs math.

Y. Bartal. Probabilistic Approximation of Metric Spaces and its Algorithmic Applications. FOCS 1996.

 

Probabilistic Approximation of Metrics by Trees

J. Lee. Random Tree Embeddings. Blog post from tcs math.

A. Gupta. Randomized Algorithms. Lectures 15 & 16.

Y. Bartal. Probabilistic Approximation of Metric Spaces and its Algorithmic Applications. FOCS 1996.

J. Fakcharoenphol, S. Rao, K. Talwar. A Tight Bound On Approximating Arbitrary Metrics By Tree Metrics.

J. Fakcharoenphol, S. Rao, K. Talwar. Approximating metrics by tree metrics. SIGACT News.

D. Williamson and D. Shmoys­. The Design of Approximation Algorithms. Section 8.5.