General Information
Course Website: http://www.math.uwaterloo.ca/~harvey/W11/
Lecture Time: Tuesdays
& Thursdays, 11:30am12:50pm
Lecture Room: MC 4042
Instructor: Prof. Nicholas Harvey, MC 6068, harvey@math.uwaterloo.ca
Assignments
·
Assignment 1, due Thursday
January 27^{th}.
·
Assignment 2, due Thursday
March 11^{th}.
·
Assignment 3, due Thursday
March 31^{st}.
Lecture Topics

Date 
Topics 
Reading
in Textbooks 
1 
1/4 
Review,
Max Dicut, Markov's inequality 
MU 1.2,
2.12.4, 3.1 
2 
1/6 
Amplification
by independent trials, Chernoff bound, Union bound,
Balls and bins 
MU
4.14.2 & 5.2, MR 4.1 & 3.1, DP 1 & 2.2, AS App. A 
3 
1/11 
Randomized
complexity classes, BPP amplification, BPP has polynomial size circuits 
MR 1.5
& 2.3 
4 
1/13 
Congestion
minimization, Discrepancy, Codes of large distance 
MU 4.4, MR 4.1 & 4.3, 
5 
1/18 
Dimensionality
reduction by the JohnsonLindenstrauss lemma 
DP 2.5 
6 
1/20 
Estimating
L2norm in data streams, Nearest neighbours in high dimensions 

7 
1/25 
SchwartzZippel Lemma, Polynomial identity testing 
MR 7.2 
8 
1/27 
Kakeya sets 

9 
2/1 
Minimum
cuts via contractions 
MU 1.4,
MR 1.1 & 10.2 
10 
2/3 
Graph
skeletons and sparsifiers 

11 
2/8 
Concentration
for matrices by the AhlswedeWinter inequality 

12 
2/10 
Spectral sparsifiers 

13 
2/15 
Chebyshev's inequality, Pairwise independence 
MU
3.23.3, 13.113.2 
14 
2/17 
Perfect
hashing, NPcomplete problems with unique solutions 
MU
13.313.4, MR 8.5 
15 
3/1 
Martingales,
Concentration by Azuma’s inequality 
MU 12.1
& 12.4, MR 4.4, 
16 
3/3 
Method of
bounded differences, Balls and bins, chromatic number. 
MU 12.5, MR
4.4.34.4.4, AS 7.2, 7.47.5, DP 5.35.4 & 6.3 
17 
3/8 
Online
bipartite matching 

18 
3/10 
Expanders
and super concentrators 

19 
3/15 
Random
partitions of metric spaces 

20 
3/17 
Random
embeddings of metric spaces into trees 

21 
3/22 
Embedding
metric spaces into L1, Sparsest Cut 

22 
3/24 
Rounding
the LeightonRao Relaxation. Low congestion trees. 

23 
3/29 
Low
congestion trees, Bisection 

24 
3/31 
Nonbipartite
matching 
Further Reading
Review of Discrete
Probability
E. Lehman, F. T. Leighton and A.
Meyer. Mathematics for Computer Science.
Ch 1418.
C. McDiarmid. Concentration. Sections 1 & 2.
Balls and Bins
M. Raab and A. Steger. “Balls into Bins”  A Simple and Tight Analysis.
Randomized Complexity
Classes
S. Arora
and B. Barak. Computational
Complexity: A Modern Approach. Chapter 7.
M. Sudan. Advanced Complexity Theory. Lecture 10 and Lecture
11.
Circuits
S. Arora
and B. Barak. Computational
Complexity: A Modern Approach. Chapter 6.
M. Sudan. Advanced Complexity Theory. Lecture 3.
Congestion Minimization
D.
Williamson and D. Shmoys. The
Design of Approximation Algorithms. Section 5.11.
Codes
M. Sudan. Coding Theory. Lecture 1 and Lecture 9.
Dimensionality
Reduction by JohnsonLindenstrauss
M. Goemans. Metric
Embeddings. Lecture
1 and Lecture 6.
A. Gupta
and R. Ravi. Algorithmic Applications of Metric Embeddings. Lecture 15.
P. Indyk.
Sketching, Streaming, and Sublinear Space Algorithms. Lecture 2.
P. Indyk.
Geometric
Computation. Lecture 17.
Nearest Neighbors
P. Agarwal. Geometric
Optimization. Lecture 25.
P. Indyk
and R. Motwani. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.
STOC 1998.
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.
Matching Algorithms
L.
Lovasz. On
determinants, matchings and random algorithms. FCT 1979.
T. Tao. Dvir’s Proof of
the finite field Kakeya conjecture. Blog post from What’s new.
Z. Dvir. From randomness extraction to rotating needles. SIGACT News 2009.
Z. Dvir. On
the size of Kakeya sets in finite fields.
Minimum Cuts and Graph
Skeletons
D. Karger. Random Sampling in Cut, Flow and Network Design Problems. STOC 1994. Section
2 and Appendix A.
Sparsifiers
A. Benczur and D. Karger.
Randomized
Approximation Schemes for Cuts and Flows in Capacitated Graphs. STOC 1996.
Concentration for
Matrices by AhlswedeWinter
R. Vershynin. A
note on sums of independent random matrices after AhlswedeWinter.
T. Tao. The GoldenThompson Inequality.
Blog post from What’s
new.
Spectral Sparsifiers
D. Spielman and N. Srivastava. Graph Sparsification
by Effective Resistances. STOC 2008.
Pairwise Independence
M. Luby and A. Wigderson.
Pairwise Independence and Derandomization. Sections 1, 2, 3.2.
J. Snell. Gambling, probability and martingales.
R. Mansuy. The
Origins of the Word “Martingale”.
C. McDiarmid. Concentration. Sections 3.1 & 3.3.
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.
Online Bipartite
Matching
B. Birnbaum and C. Mathieu. Online
Bipartite Matching Made Simple. SIGACT News 2008.
R. Karp,
U. Vazirani
and V. Vazirani. An
Optimal Algorithm for Online Bipartite Matching.
STOC 1990.
S. Hoory, N. Linial
and A. Wigderson.
Expander Graphs and Their Applications.
Chapter 1.
Low Diameter Partitions
J. Lee. Random Partitions of Metric Spaces.
Blog post from tcs math.
G. Calinescu, H. Karloff and Y. Rabani. Approximation Algorithms for the 0Extension Problem. SODA 2001.
Random Embeddings into
Trees
J. Lee. Random tree embeddings. Blog post from tcs math.
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. STOC
2003.
D.
Williamson and D. Shmoys. The
Design of Approximation Algorithms. Section 8.5.
Sparsest Cut
L. Trevisan. The LeightonRao Relaxation. Blog post from in
theory.
D.
Williamson and D. Shmoys. The
Design of Approximation Algorithms. Section 15.1.
Low Congestion Trees
& Graph Bisection
R. Andersen and U.
Feige. Interchanging distance and capacity in probabilistic mappings.
D.
Williamson and D. Shmoys. The
Design of Approximation Algorithms. Section 15.2 and Section 15.3.
H. Räcke. Optimal Hierarchical Decompositions for Congestion Minimization in
Networks. STOC 2008.
N. Harvey. Algebraic Algorithms for Matching and Matroid
Problems. FOCS 2006.