Selected Topics in Discrete Mathematics -- Fall 2007
Approximate isometries of finite metric spaces

Meeting Time/Place: Monday,Thursday 2nd (10:20-11:40) in Hill 425
Instructor: Professor Michael Saks
Office: Hill 304 and Hill 430
e-mail:saks@math.rutgers.edu

Basic Course Information

Finite metric spaces are of interest in discrete mathematics, geometry and analysis, and have applications to a variety of problems in algorithms. In recent years, there has been much research activity centered around the problem of mapping an arbitrary finite metric spaces into a "nice" metric space in such a way distances are well approximated. This course will be an introduction to this area.

The material for the course will be taken from several sources. See the list of references below.

Any mathematics Ph.D. student who has finished their first year is prepared for this course. Other students should talk to me.

There will be homework assignments and no exams in the course.

Homework


Assignment 1 (Target due date: 10/25/07) pdf 10/11 version
Assignment 2 (Due date: 12/16/07) pdf 1/10/2008 version

Homework Format
To make it easier for me to read and comment upon, please follow these guidelines on your written work:
  • Use standard 8 by 11 sheets of paper with no ragged edges.
  • Your name should appear at the top of each page. Pages should be numbered and stapled together.
  • You should have a cover page that gives your name and a table with three columns. The first column lists each of the assigned problems in the order that they appear on the assignment (whether you did them all or not). The second column contains the number of the page of your work where the solution to the problem appears (or the words ``Not done'' if you did not do it.) The third column is left blank for me to record the score.

    Collaboration on homework
    You will get the most benefit from the problem assignments if you do most of the work on your own. However, there is also a benefit to be gained by discussing problems with other students or with me, particularly if you are stuck on a problem. Here is my policy on outside help:
  • No written work pertaining to an assignment is to be given to or obtained from others.
  • You may discuss problems with others, but the final write-up of your solutions should be done independently. This means that you should not be sitting with other students when you write up your solutions.
  • I am fairly generous about giving hints and partial solutions to homework in my office hours. However, my policy is that you can't take notes on my hints, you must understand them sufficiently to be able to reconstruct them yourself later.
  • The solutions to a number of the problems in this course can be found in some of the books on reserve or in other literature. The problems are intended for you to do, not to look up. If you do read about a problem elsewhere, then you should (a) do your write-up of the problem ``closed book'' and (b) properly acknowledge your use of the book (see below).
  • Discussions about a problem, hints received, etc. (including office hour hints), reference to books other than the course text, must be acknowledged in your homework. This means that immediately following your written solution, you should write something like ``Acknowledgement: John Smith gave me a hint on this problem'', ``Acknowledgement: I worked with Jane Jones on this problem'', or whatever is appropriate.

    References

    (This list is under construction.)


  • J. Matousek, Lectures on Discrete Geometry, Springer 2002 (on library reserve)
    Chapter 15, Embedding finite metric spaces into Euclidean spaces, will be the starting point for the course. Here is a a revised version of this chapter. The chapter is largely self-contained but does have occasional references to previous chapters of the book.
  • J. Matousek, editor, Open problems in low-distortion embeddings of finite metric spaces.
    A large collection of open research problems in the area.
  • P. Indyk and J. Matousek, Low-distortion embeddings of finite metric spaces
    A short (and terse) overview of the area written in 2002, so it's already out-of-date.
  • N. Linial, Finite Metric Spaces and Low dimensional embeddings , lecture notes, 2004 Barbados Workshop on Computational Complexity.
  • Nati Linial, Finite Metric Spaces - Combinatorics, Geometry and Algorithms Proceedings of the International Congress of Mathematicians III, 573--586 Beijing, 2002.
  • S. Vempala, The Random Projection Method, AMS, 2004. (On library reserve)
  • S. Arora, S. Rao and U. Vazirani, Expander Flows, Geometric Embeddings, and Graph Partitionings.
  • J. Lee, Distance scales, embeddings, and metrics of negative type.
  • S. Chawla, A. Gupte and H. Racke, Approximations for Generalized Sparsest Cut and Embeddings of L2 into L1. , to appear in J.AMS.
  • S. Arora, J. Lee, A. Naor Euclidean distortion and the Sparsest Cut , to appear in J.AMS.