General Information
Course Website: http://www.math.uwaterloo.ca/~harvey/W11/
Lecture Time: Tuesdays
& Thursdays, 11:30am-12:50pm
Lecture Room: MC 4042
Instructor: Prof. Nicholas Harvey, MC 6068, harvey@math.uwaterloo.ca
Assignments
·
Assignment 1, due Thursday
January 27th.
·
Assignment 2, due Thursday
March 11th.
·
Assignment 3, due Thursday
March 31st.
Lecture Topics
|
|
Date |
Topics |
Reading
in Textbooks |
|
1 |
1/4 |
Review,
Max Dicut, Markov's inequality |
MU 1.2,
2.1-2.4, 3.1 |
|
2 |
1/6 |
Amplification
by independent trials, Chernoff bound, Union bound,
Balls and bins |
MU
4.1-4.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 Johnson-Lindenstrauss lemma |
DP 2.5 |
|
6 |
1/20 |
Estimating
L2-norm in data streams, Nearest neighbours in high dimensions |
|
|
7 |
1/25 |
Schwartz-Zippel 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 Ahlswede-Winter inequality |
|
|
12 |
2/10 |
Spectral sparsifiers |
|
|
13 |
2/15 |
Chebyshev's inequality, Pairwise independence |
MU
3.2-3.3, 13.1-13.2 |
|
14 |
2/17 |
Perfect
hashing, NP-complete problems with unique solutions |
MU
13.3-13.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.3-4.4.4, AS 7.2, 7.4-7.5, DP 5.3-5.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 Leighton-Rao Relaxation. Low congestion trees. |
|
|
23 |
3/29 |
Low
congestion trees, Bisection |
|
|
24 |
3/31 |
Non-bipartite
matching |
Further Reading
Review of Discrete
Probability
E. Lehman, F. T. Leighton and A.
Meyer. Mathematics for Computer Science.
Ch 14-18.
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 Johnson-Lindenstrauss
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 Sub-linear 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.
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.
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 Ahlswede-Winter
R. Vershynin. A
note on sums of independent random matrices after Ahlswede-Winter.
T. Tao. The Golden-Thompson 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. On-line
Bipartite Matching Made Simple. SIGACT News 2008.
R. Karp,
U. Vazirani
and V. Vazirani. An
Optimal Algorithm for On-line 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 0-Extension 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 Leighton-Rao 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.