Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**Date and Time**: Tuesday, June 28, 2011, 12:15 pm

**Duration**: This information is not available in the database

**Location**: CAB G51

**Speaker**: Andrea Francke

During the last two decades or so, low-distortion embeddings became recognized as a useful toolkit for designing efficient algorithms [Indyk '01]. A project that has received considerable attention is to embed the edit distance metric into the normed space l_1. A subcase of this is to consider the Ulam metric, that is, the metric space of all permutations of length n together with the edit distance, and to embed it into l_1. Krauthgamer and Charikar have shown in 2006 that this is possible with distortion O(log n), which is close to optimal. After a brief introduction on metric embeddings, I will present their embedding and parts of the analysis as a nice example for a metric embedding with surprising connections to elements from the analysis of randomized quicksort, as prominently featured in the "Algorithms, Probability and Computing" course.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login