Time+Place: | Tuesday 10/11/2015 14:30 Room 337-8 Taub Bld. |

Title: | Vertex Sparsification of Cuts, Flows, and Distances |

Speaker: | Robert Krauthgamer - COLLOQUIUM LECTURE http://www.wisdom.weizmann.ac.il/~robi/ |

Affiliation: | Weizmann Institute of Science |

Host: | Nir Ailon |

A key challenge in designing graph algorithms is to "compress" a graph G so as to preserve some of its basic properties, such as distances and cuts. Both spanners [Peleg and Schaffer, 1989] and cut sparsifiers [Benczur and Karger, 1996] fall into this category, as they reduce the number of edges in G without changing any distance or cut by more than a small factor. I will discuss another flavor of this challenge, which asks instead to reduce the number of vertices. Specifically, given a graph G and k terminal vertices, we wish to construct a small graph G' that contains the terminals, such that all cuts/flows/distances between the terminals are equal in G and in G'. Can we bound the size of G' by a function of k? And what if G' only needs to approximate G (say within 1+epsilon)? I plan to survey recent progress in this emerging area. Short Bio: Robert Krauthgamer is an Associate Professor in the Faculty of Mathematics and Computer Science at The Weizmann Institute of Science, Israel. He received his PhD from the Weizmann Institute in 2001, and worked at the IBM Almaden Research Center as a Research Staff Member before returning to Weizmann as a faculty member in 2007. His research interests are in algorithms, especially those involving Massive Data Sets, Combinatorial Optimization, Approximation Algorithms, and Average-case Analysis of Heuristics. Desserts will be served from 14:15 Lecture starts at 14:30