CPSC 536N: (Graduate) Randomized Algorithms

2021-22 Winter Term 2

General Information

Lecture Time: Tue, Thu 11am-12:30pm
Instructor:
Prof. Nicholas Harvey, X851, nickhar@cs.ubc.ca

TAs: Victor Sanches Portella

 

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

·        CPSC 536N, Winter 2015

·        CPSC 436R, Fall 2021