[Colloquium] TTI-C Talk: Anastasios Sidiropoulos, University of Toronto

[Julia MacGlashan]

REMINDER

When:             Tuesday, March 24th @ 11:00am (lunch will be provided
after talk)

Where:            6045 S Kenwood Ave, TTI-C Conference Room #526 (5th Floor)

Who:               Anastasios Sidiropoulos (University of Toronto)

Title:                Algorithmic metric embeddings


We consider the problem of computing a low-distortion embedding of a finite
metric space into low-dimensional and topologically simple spaces.  It has
been shown by Matousek [Mat90] that for any d\geq 1, any n-point metric can
be embedded into R^d with distortion ~O(n^{2/d}) via a random projection,
and that in the worst case this bound is essentially optimal. This clearly
also implies an ~O(n^{2/d})-approximation algorithm for minimizing the
distortion. We show that for any fixed d\geq 2, there is no polynomial-time
algorithm for embedding into R^d, with approximation ratio better than
Omega(n^{1/(22d)}), unless P=NP. Our result establishes that random
projection is not too far from the best possible approximation algorithm for
this problem.

We also give some positive results by resorting to the relaxed notion of
stochastic embeddings.  Such mappings are allowed to be randomized, and the
distance between every pair of points is required to be approximately
preserved in expectation.  We exhibit a novel approach for topological
simplification of a metric space via stochastic embeddings.  More precisely,
we show how to stochastically embed bounded-genus graphs into planar graphs
with constant distortion, and we discuss extensions to arbitrary minor-free
graph families.  This result is based on a structural theorem of Robertson
and Seymour [RS83], and leads to a simplification of the
Gupta-Newman-Rabinovich-Sinclair conjecture [GNRS04] which characterizes all
graphs that have an O(1)-approximate multi-commodity max-flow/min-cut
theorem.

Contact:          Julia Chuzhoy, TTI-C		cjulia at tti-c.org
834-2572




-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20090323/c92c4848/attachment.htm