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