#### Algorithms through geometric lens (CSE 599 I)

- Instructor: Ilya Razenshteyn
- Time: Tuesday, Thursday 4:30—5:50pm
- Room: CSE 303
- Office hours: by appointment

##### Course description

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

##### Prerequisites

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.

##### 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