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

Abstract:


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