University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Vertex sparsifiers: New results from old techniques (and some open questions)

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Vertex sparsifiers: New results from old techniques (and some open questions)

Download to your calendar using vCal

If you have a question about this talk, please contact Mustapha Amrani .

Discrete Analysis

Given a capacitated graph G = (V,E) and a set of terminals $K ubseteq V$, how should we produce a graph H only on the terminals K so that every (multicommodity) flow between the terminals in G could be supported in H with low congestion, and vice versa? (Such a graph H is called a flow-sparsifier for G.) What if we want H to be a ``simple’’ graph? What if we allow H to be a convex combination of simple graphs? And is the question easier if we wanted H to maintain the distances among the terminals (rather than flows)?

Joint work with Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Raecke, Inbal Talgam-Cohen and Kunal Talwar.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

https://meet.google.com/hmo-aaio-agh Computer Lab, FW11 and Online (zoom link below) Cambridge University First Aid Society

Other talks

Cambridge AI in Medicine Seminar - April 2026 Discovery Investigations: Science, Empire and the Making of the British South Atlantic Advances in Label-Free High-Resolution Molecular Imaging using J Series III Cluster SIMS Title to be confirmed: ANUBIS The Jiangmen Underground Neutrino Observatory (JUNO): Status and First Physics Results Title to be confirmed
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity