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
Fri Mar 18 12:13:22 PDT 2022

Theory folks,

Quick reminder that we will have a special seminar at 2pm today (details
If you are unable to join in person, but would like to follow along, you
can join virtually via zoom:


On Thu, Mar 17, 2022 at 12:03 PM Moses Charikar <moses at>

> 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!
> Cheers,
> Moses
> 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