## Algorithms through Geometric Lens (COMS E6998-5)

• Instructors: Alexandr Andoni and Ilya Razenshteyn
• TA: Rex Lei
• Time: MW 4:10-5:25pm
• Room: CEPSR 415
• Office hours: Alex Tue 4:30—6:30pm in Mudd 420, Ilya Thu 2:30—4:30pm in Mudd 464, Rex Mon 1—3pm in CS help room (Mudd 1st floor).

#### Class Description

See the official course information.

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.

The class may be counted as theory breadth requirement (with instructor's approval). Grading is based on problem sets and a final project.

#### 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. COMS 4231 (Analysis of Algorithms) or equivalent is highly recommended, but not required if you have solid math background.

Undergradute students and students from other departments are welcome.

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