Algorithms through geometric lens (CSE 599-I)
- Instructor: Ilya Razenshteyn
- Time: Tuesday, Thursday 4:30—5:50pm
- Room: CSE 305
- Office hours: by appointment
See the official course description.
Many classic and modern algorithms benefit from geometric techniques and tools even though the initial problem might have nothing to do with geometry. In this class, we will cover a number of such examples.
As an example, suppose that we would like to partition a given graph in $k$ pieces of similar size while having only few edges between the pieces.
This is a classic hard problem which is extremely useful in many areas, from scientific computing to route planning in road networks. As it turns out,
one can obtain high-quality partitions by computing certain $k$-dimensional vectors for each vertex of a graph using linear algebra,
and then performing a sophisticated geometric procedure on these vectors.
Grading will be based on 2—3 problem sets and a final project.
The class should be ideal for CS graduate students specializing in Theoretical Computer Science or Machine Learning.
However, undergradute students and students from other departments are welcome.
A previous offering of this class was co-taught with Alexandr Andoni at Columbia University.
Mathematical maturity is a must: the class is based on theoretical ideas and is proof-heavy. You are expected to be able to read and write formal mathematical proofs.
Some familiarity with algorithms and randomness will be assumed as
Tentative list of topics
- Sketching/streaming algorithms for numeric and graph streams
- Dimension reduction with applications
- Data structures for similarity search
- Graph algorithms based on semidefinite programming
- Spectral graph algorithms
- Metric embeddings and their applications
- Distance oracles
- Algorithms for discrepancy minimization
- September 27: Introduction, Tug of War Sketch (notes)
- October 2: Count-Sketch, Chernoff Bounds, $\ell_0$-Sampling (notes)
- October 4: $\ell_0$-Sampling, Graph Sketching, Dimension Reduction (notes)
- October 9: Measure Concentration (notes)
- October 11: Dimension Reduction, Fast Dimension Reduction (notes)
- October 16: Randomized Numerical Linear Algebra (notes), problem set 1 is out
- October 18: Nearest Neighbor Search, Locality-Sensitive Hashing (notes)
- October 23: Nearest Neighbor Search, Locality-Sensitive Hashing (notes)
- October 25: Locality-Sensitive Hashing, Nearest Neighbor Search for $\ell_\infty$ (notes)
- October 30: Maximum Cut, Coloring (notes) problem set 1 is due
- November 1: Coloring, Sparsest Cut, Cheeger's Inequality (notes)
- November 6: Cheeger's Inequality, Sparsest Cut (notes) project proposal is due, problem set 2 is out
- November 8: Sparsest cut, Bourgain's theorem (notes)
- November 13: Multicut, Padded Decompositions (notes)
- November 15: Padded Decompositions, Nonlinear Dvoretzky Theorem, Distance Oracles (notes)
- November 20: Distance Oracles (notes) problem set 2 is due
- November 22: no class (Thanksgiving!)
- November 27: Discrepancy Minimization (notes)
- November 29: Constructive Discrepancy Minimization guest lecture by Sami Davies
- December 4: Optimal Sorting of a Partial Order (notes)
- December 6: Class Summary, Open Problems final project is due