[Colloq] Talk-Scans Seminar Monday May 2, 2011

[panarese at ccs.neu.edu]

The College of Computer and Information Science presents: 

Scans Seminar 


Where: WVH366 
When: 2 - 3 PM, Monday May 2, 2011 

Title: Random Sampling and Cuts in Graphs: Three Combinatorial Proofs 

Speaker: David Karger, MIT 

Abstract: 
I'll synthesize work showing that randomly sampling the edges of an undirected graph 
preserves cut values. I'll give three distinct proofs, based on random contraction, tree 
packing, and network reliability, that the values of cuts are tightly concentrated around 
their expectations when those expectations are sufficiently large. I'll give a 
combinatorial construction for sparsifying any n-vertex undirected graph down to O(n log 
n) edges with only small perturbations in cut value and show how it can be used in fast 
algorithms for approximate and exact maximum flow computations. While one can achieve 
slightly better sparsification using algebraic techniques, I believe these combinatorial 
methods offer useful insights and may yield more in the future. The talk is 
self-contained, requiring only elementary knowledge of combinatorics and probability. 

Bio: 
David Karger (A.B. 1989, Harvard University, Ph.D. 1994, Stanford 
University) is a Professor of Computer Science and a member 
of the Computer Science and Artificial Intelligence Laboratory at the 
Massachusetts Institute of Technology. His research interests include 
algorithms and their applications, networking, computer systems, machine learning 
and human computer interaction. 








\