2021-22
Winter Term 2
General Information
Lecture Time: Tue, Thu
11am-12:30pm
Instructor: Prof. Nicholas Harvey, X851,
nickhar@cs.ubc.ca
Lectures
·
Jan 11-20: On Zoom. The link can be found in Piazza.
·
Jan 25 onwards: In person?
Piazza
Piazza signup link: http://piazza.com/ubc.ca/winterterm22021/cpsc536n
Approximate List of Topics
·
Approximation
Algorithms for Combinatorial Optimization problems
o
Max
Cut, Set Cover
·
Concentration
o
Chernoff
& Hoeffding bounds, Proofs
o
Applications:
Congestion minimization, Error-correcting codes
·
High-dimensional
data
o
Johnson-Lindenstrauss, Fast Johnson-Lindenstrauss,
Nearest Neighbours in Euclidean Space, Streaming
algorithms to estimate L2, Locality Sensitive Hashing for Hamming Distance and
p-norms
·
Graphs
o
Skeletons
and Sparsifiers
o
Expanders,
Superconcentrators, Sipser-Spielman
codes
o
Max
Cut via Semidefinite Programming
o
Online
Bipartite Matching
·
Low
Randomness
o
Chebyshev’s
Inequality, Pairwise Independence, k-wise Independence. Valiant-Vazirani theorem.
o
Derandomization: Conditional Expectation, Pessimistic
Estimators, Congestion minimization.
·
Streaming
algorithms
o
Alon-Mathias-Szegedy algorithm to estimate L2
o
Distinct
Elements using Beta random variables
o
Count-Sketch
for Heavy Hitters
·
Martingales
o
Azuma’s
Inequality, Methods of Bounded Differences, Balls and Bins
o
Concentration
for SGD
·
Algebraic
Methods
o
Schwartz-Zippel
Lemma, Polynomial Identity Testing
o
Bipartite
and Non-bipartite Matching
·
Probabilistic
Method
o
Existential
Lovasz Local Lemma, Algorithmic Local Lemma
·
Property
Testing
o
Sortedness, Maximal Matching Size
·
Random
Matrices
o
Ahlswede-Winter Inequality, Spectral Sparsifiers
·
Metric
Spaces
o
Low-distortion
Embeddings, FRT Trees, Embedding into L1, Sparsest Cut
Related Offerings