CS Colloquium- Julia Chuzhoy

Dr. Julie ChuzhoySchool of MathematicsThe Institute for Advanced StudyTitle: Cuts and Flows in Directed GraphsAbstract:Cuts and flows are among the most basic graph theoretic notions.
Applications that require solving graph cut or flow problems arise in almost every area of computer science. The study of the connection between flows and cuts dates back to the late fifties when Ford and Fulkerson proved that in the single-commodity environment, minimum cut equals maximum flow in any graph. A natural generalization of this result would be establishing the relationship between flows and cuts in the presence of multiple commodities. This relationship is usually expressed via the notion of flow-cut gap:
the maximum ratio, achievable for any graph, between the maximum multi-commodity flow and the corresponding cut value, called minimum multicut.Flow-cut gaps have been extensively studied for more than five decades now, and they are widely used in the design and the analysis of algorithms. One of the major breakthroughs in this area is a complete understanding of the flow-cut gap in undirected graphs, which was proved to be logarithmic. In spite of this success, the flow-cut gaps have remained poorly understood in directed graphs. In particular, it has remained an open question whether the flow-cut gap in directed graphs is also logarithmic. In this talk we will answer this question in the negative by showing that, in sharp contrast to the undirected case, the flow-cut gap in directed graphs is polynomial.Bio:Julia Chuzhoy is a member in the School of Mathematics at the Institute for Advanced Study. She received her Ph.D. in Computer Science from Technion, Israel, and spent two years as a postdoctoral associate at MIT and University of Pennsylvania. Chuzhoy's research area is theoretical computer science, with the main emphasis on design and analysis of algorithms, approximation of NP-hard problems and hardness of approximation proofs.Hosted by David KempeSnacks will be served

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: Nancy Levien