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

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

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 for numeric and graph streams
• Dimension reduction
• Data structures for similarity search
• Fast algorithms for linear algebra problems and for kernel-based machine learning methods
• Finding sparse (multi-way) cuts in graphs via convex relaxations/spectral partitioning
• Metric embeddings and their applications
• Algorithms for graph coloring
• Distance oracles
• Algorithms for discrepancy minimization