- Cutting corners cheaply, or...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in October 2013

## Cutting corners cheaply, or how to remove Steiner points

**Speaker:**
Huy Le Nguyen
, Princeton

**Date:**
Wednesday, October 09, 2013

**Time:**
4:00 PM to 5:00 PM
** Note: all times are in the Eastern Time Zone**

**Public:**
Yes

**Location:**
32-G575

**Event Type:**

**Room Description:**

**Host:**
Ronitt Rubinfeld

**Contact:**
Ilya Razenshteyn, ilyaraz@csail.mit.edu

**Relevant URL:**
http://www.ilyaraz.org/acseminar/

**Speaker URL:**
None

**Speaker Photo:**

None

**Reminders to:**
compalgsem@lists.csail.mit.edu, theory-seminars@lists.csail.mit.edu

**Reminder Subject:**
TALK: Cutting corners cheaply, or how to remove Steiner points

Our main result is that the Steiner Point Removal (SPR) problem can always be solved with polylogarithmic distortion, which resolves in the affirmative a question posed by Chan, Xia, Konjevod, and Richa (2006). Specifically, we prove that for every edge-weighted graph $G = (V,E,w)$ and a subset of terminals $T \subseteq V$, there is a graph $G'=(T,E',w')$ that is isomorphic to a minor of $G$, such that for every two terminals $u,v\in T$, the shortest-path distances between them in $G$ and in $G'$ satisfy $d_{G,w}(u,v) \le d_{G',w'}(u,v) \le O(\log^6|T|) \cdot d_{G,w}(u,v)$. Our existence proof actually gives a randomized polynomial-time algorithm.

Our proof features a new variant of metric decomposition. It is well-known that every finite metric space $(X,d)$ admits a $\beta$-separating decomposition for $\beta=O(\log |X|)$, which roughly means for every desired diameter bound $\Delta>0$ there is a randomized partitioning of $X$, which satisfies the following separation requirement: for every $x,y \in X$, the probability they lie in different clusters of the partition is at most $\beta\,d(x,y)/\Delta$. We introduce an additional requirement, which is the following tail bound: for every shortest-path $P$ of length $d(P) \leq \Delta/\beta$, the number of clusters of the partition that meet the path $P$, denoted $Z_P$, satisfies $\Pr[Z_P > t] \le 2e^{-\Omega(t)}$ for all $t>0$.

Joint work with Lior Kamma and Robert Krauthgamer.

**Research Areas:**

**Impact Areas:**

*This event is not part of a series.*

Created by Ilya Razenshteyn at Monday, September 23, 2013 at 12:12 PM.