Seminar on Algorithms and Geometry (semester 2014B)

Weizmann Institute of Science

[Course description] [Announcements] [Lectures schedule] [Assignments] [Reading material]

Course description

Instructor: Robert Krauthgamer

When and where: Wednesday, 4:15-6:00pm, Ziskind Lecture Room 1

First class: March 12, 2014

FGS code: 20144182

Syllabus: This seminar will cover recent algorithmic topics that involve geometric concepts and techniques, including algorithms for nearest neighbor search, dimensionality reduction, traveling salesman problem, metric embeddings, metric decompositions, and their applications to combinatorial algorithms such as approximation algorithms for graph partitioning.

Prerequisites: Basic knowledge of algorithms, at an undergraduate level, is required, and familiarity with Euclidean geometry, probability theory, and linear algebra may be necessary.


Previous offering:


Lectures schedule

  1. 2014-03-12: Doubling dimension and Nearest Neighbor Search (to be continued)
    [homework: none]  [reading: lecture notes #1

    2014-03-19: no class (faculty retreat)

  2. 2014-03-26: Doubling dimension and Nearest Neighbor Search (continued)
    [homework: problem set #1]  [reading: lecture notes #2; papers KL04, BKL06, HM06, CG06]

  3. 2014-04-02: Dimension reduction via random projections
    [homework: none]  [reading: Harvey, lecture #6; Goemans, lecture #6; my previous class, scribe #4]
  4. 2014-04-09: Approximating MAX-CUT via Semidefinite Programming
    [homework: problem set #2] [reading: Trevisan, lecture #7 (a guest lecture I gave); Williamson-Shmoys, Chapters 6.1-6.2]
  5. 2014-04-16: no class (Passover)

  6. 2014-04-23: Polynomial Time Approximation Schemes for Euclidean Traveling Salesman
    [paper presented by Ami Mor + Dima Kogan] 
  7. 2014-04-30: no class (cancelled)

  8. 2014-05-07: Low-distortion embeddings and probabilistic embedding into dominating trees
    [homework: none]  [reading: Fakcharoenphol-Rao-Talwar]
  9. 2014-05-14: Probabilistic embedding into dominating trees (cont'd)
    [homework: problem set #3] [reading: Fakcharoenphol-Rao-Talwar]
  10. 2014-05-21: Approximating Multicut -- LP Rounding via Tree Embeddings;
  11. 2014-05-28: no class (cancelled)

    2014-06-04: no class (SHAVUOT)

  12. 2014-06-11: Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering
    [paper presented by Matan Karklinsky + Noam Arkind] 
  13. 2014-06-18: Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
    [paper presented by Idan Himlich]
  14. 2014-06-25 (morning): Excluded minors, network decomposition, and multicommodity flow
    [paper presented by Lior Kamma]
  15. 2014-06-25 (regular time): Planar Separators
    [reading: lecture notes #12; Sommer, lecture #3


(Should be turned in within two weeks)

Reading material

Surveys and chapters:

Classes in other institutions:

Suggested papers for presentations (in crude categorization):

Low-distortion embeddings:
Nearest Neighbor Search (NNS):

Algorithms for processing metric spaces (including low-dimensional, doubling, or graphical):

Graph partitioning algorithms: