General Information
Course Website: http://www.cs.ubc.ca/~nickhar/W12
Lecture Time: Tuesdays
& Thursdays, 9:30am11:00am
Lecture Room: DMP 101
Instructor: Prof. Nicholas
Harvey, X851, nickhar@cs.ubc.ca
·
Proposal Due Tuesday February 28^{th}, in class.
Assignments
·
Assignment 1: Due
Thursday February 2^{nd}, in class.
·
Assignment 2: Due
Thursday March 1^{st}, in class.
·
Assignment 3: Due Tuesday
April 3^{rd}, 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.12.4 

2 
1/10 
Markov’s
Inequality, Amplification
by Independent Trials, Chernoff Bound 
MU 3.1, 4.14.2, MR 3.2, 4.1 

3 
1/12 
Balls and
Bins, Congestion Minimization, Negative Binomial Distribution 
MU 5.2,
MR 4.3 

4 
1/17 
Quicksort,
SkipNet 
DP 2.4 

5 
1/19 
SkipNet
Analysis, Consistent Hashing 

6 
1/24 
Dimensionality
Reduction by the JohnsonLindenstrauss Lemma 
DP 2.5 

7 
1/26 
Streaming
Algorithms, Nearest Neighbor 

8 
1/31 
Compressed
Sensing 

9 
2/2 
Polynomial
Identity Testing by the SchwartzZippel Lemma 
MR 7.2 

10 
2/7 
Minimum
Cuts by the Contraction Algorithm 
MU 1.4,
MR 1.1 & 10.2 

11 
2/9 
Graph
Sparsifiers 

12 
2/14 
Concentration
for Sums of Random Matrices 

13 
2/16 
The
AhlswedeWinter Inequality 

14 
2/28 
Spectral
Sparsifiers 

15 
3/1 
Lowrank
Approximation of Matrices 

16 
3/6 
Derandomization:
Method of Conditional Expectations, Method of Pessimistic Estimators 
MU 6.3,
MR 5.6 

17 
3/8 
Chebyshev’s
Inequality, Pairwise Independence 
MU
3.23.3, 13.113.2, MR 3.2 & 3.4 

18 
3/13 
Perfect
Hashing 
MU 13.3 

19 
3/15 
The
Lovasz Local Lemma 
MU 6.7,
MR 5.5, AS 5 

20 
3/20 
Expanders,
Superconcentrators 
MR 6.7 

21 
3/22 
Property
Testing 

22 
3/27 
Random
Partitions of Metric Spaces 

23 
3/29 
Random
Partitions of Metric Spaces, Continued 

24 
4/3 
Probabilistic
Approximation of Metrics by Trees 

25 
4/5 
Online
Steiner Tree 
Further Reading
Review of Discrete
Probability
E. Lehman, F. T. Leighton and A. Meyer. Mathematics for
Computer Science. Ch 1418.
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.
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 JohnsonLindenstrauss
M. Goemans.
Metric Embeddings. Lecture 6.
A. Gupta
and R. Ravi. Algorithmic
Applications of Metric Embeddings. Lecture 15.
P. Indyk. Sketching,
Streaming, and Sublinear Space Algorithms. Lecture
2.
S. Muthukrishnan. Data streams: algorithms and
applications.
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. Nearoptimal hashing
algorithms for approximate nearest neighbor in high dimensions.
P. Indyk. Sketching,
Streaming, and Sublinear 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.
SchwartzZippel
& Polynomial Identity Testing
R. Lipton.
The
Curious History of the SchwartzZippel Lemma. Blog post from Gödel's Lost Letter and P=NP.
V. Kabanets. Pseudorandomness. Lecture 2.
D. Karger.
Global mincuts in RNC, and
other ramifications of a simple mincut 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 EdgeConnectivity and Random Spanning Trees. STOC 2011.
R. Hariharan and D. Panigrahi. A General Framework for Graph
Sparsification. STOC 2011.
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 AhlswedeWinter matrixvalued Chernoff bound using pessimistic estimators,
and applications. Section 2.
Spectral Sparsifiers
D. Spielman
and N. Srivastava. Graph
Sparsification by Effective Resistances. STOC 2008.
Lowrank 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.
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.
M. Luby
and A. Wigderson. Pairwise Independence and
Derandomization.
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.
S. Hoory, N.
Linial and A.
Wigderson. Expander
Graphs and Their Applications. Chapter 1.
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.