Abstract:

In this talk we discuss the relation between cut capacities
and multicommodity flows. We present bounds on the min cut to
max flow ratio, and approximation algorithms for finding low
capacity cuts. We discuss applications and fundamental open
problems. The talk is self-contained, and requires no previous 
knowledge beyond the undergraduate theory curriculum.