Thursday, Oct 18, 2:15pm, WWH-513 (note different room)

  SPEAKER:
  Yuri Makarychev

  TITLE:
  Local Global Tradeoffs in Metric Embeddings

  ABSTRACT:

  Suppose that every k points in an n point metric space X are
  D-distortion embeddable into l_1.  We give upper and lower bounds on
  the distortion required to embed the entire space X into l_1.  This
  is a natural mathematical question and is also motivated by the
  study of relaxations obtained by lift-and-project methods for graph
  partitioning problems.

  In this setting, we show that X can be embedded into l_1 with
  distortion O(D log (n/k)).  Moreover, we give a lower bound showing
  that this result is tight if D is bounded away from 1.  For D = 1 +
  delta we give a lower bound of Omega(log (n/k) / log (1/delta)); and
  for D=1, we give a lower bound of Omega(log n/(log k + log log n)).
  Our bounds improve on the results of Arora, Lovasz, Newman, Rabani,
  Rabinovich and Vempala, who initiated a study of these questions.

  Joint work with Moses Charikar and Konstantin Makarychev.

------------------------------------------------------------------------