Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] [New Location] max flow in near linear time: Tomorrow, 2-4pm

Moses Charikar moses at
Thu Mar 17 12:03:08 PDT 2022

Theory friends,

Quick reminder that Yang Liu and Li Chen will tell us about their new near
linear time max flow result *tomorrow (Fri Mar 18), 2-4pm.*

Please note the new location: *Gates 259*

Li and Yang plan to have about 30 min of slides first; the rest of the talk
will be on the whiteboard.

The room is a little smaller than our pre-pandemic theory seminar location,
with about 20 chairs and room for 30 people, so come on time!


On Sun, Mar 6, 2022 at 4:53 PM Moses Charikar <moses at> wrote:

> Theory folks,
> Mark your calendars: Our very own Yang Liu and Li Chen (visiting from
> Georgia Tech) will tell us about their new breakthrough result on max flow
> and min-cost flows on Friday, Mar 18, 2-4pm in Gates 415.
> Title and abstract are below. Hope to see you there!
> Cheers,
> Moses
> Title: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time.
> Abstract: We give an algorithm that computes exact maximum flows and
> minimum-cost flows on directed graphs with $m$ edges and polynomially
> bounded integral demands, costs, and capacities in $m^{1+o(1)}$ time. Our
> algorithm builds the flow through a sequence of $m^{1+o(1)}$ approximate
> undirected minimum-ratio cycles, each of which is computed and processed in
> amortized $m^{o(1)}$ time using a dynamic data structure.
> Our framework extends to an algorithm running in $m^{1+o(1)}$ time for
> computing flows that minimize general edge-separable convex functions to
> high accuracy. This gives an almost-linear time algorithm for several
> problems including entropy-regularized optimal transport, matrix scaling,
> $p$-norm flows, and isotonic regression.
> Joint work with Rasmus Kyng, Richard Peng, Maximilian Probst Gutenberg,
> and Sushant Sachdeva.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list