- 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 well.

- 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