Metric Embeddings and Algorithmic Applications (Autumn 2018)
Instructor: Moses Charikar (email: moses at cs)
Location and time: Tuesday and Thursday 10:30 AM – 11:50 AM, 320-220
Teaching assistant: Ofir Geri (email: ofirgeri at cs)
Please sign up on Piazza for discussions.
Office Hours
Moses: Wednesday 10:00 AM – 11:00 AM, Gates 472
Ofir: Tuesday 4:00 PM – 5:00 PM, Gates 459
Course Description
Low distortion embeddings of finite metric spaces is a topic at the intersection of mathematics and theoretical computer science. Much progress in this area in recent years has been motivated by algorithmic applications. Mapping complicated metrics of interest to simpler metrics (normed spaces, trees, and so on) gives access to a powerful algorithmic toolkit for approximation algorithms, online algorithms as well as for efficient search and indexing of large data sets. In a different vein, convex relaxations are a useful tool for graph partitioning problems; central to the analysis are metric embedding questions for certainly computationally defined metrics. In this course, we will see several classical and recent results on metric embeddings with a focus on algorithmic applications. Machine learned embeddings into Euclidean and hyperbolic spaces have recently become popular in natural language processing and (social) network analysis; we will explore these briefly.
Requirements: Two homework assignments (40%), one lecture scribe (20%), a final project (35%), and Piazza participation (5%).
Resources
Lecture Notes on Metric Embeddings, Jiri Matousek
https://kam.mff.cuni.cz/~matousek/ba-a4.pdf
Similar classes:
Yair Bartal, Nova Fandina (Hebrew University, Fall 2018-2019)
https://moodle2.cs.huji.ac.il/nu18/course/view.php?id=67720
Jiri Matousek, Uli Wagner (ETH Zurich, Spring 2010)
https://www.ti.inf.ethz.ch/ew/courses/ME10/index.html
Tim Roughgarden (Stanford, Winter 2006)
http://theory.stanford.edu/~tim/w06b/w06b.html