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


Theory folks,

Quick reminder that we will have a special seminar at 2pm today (details
below).
If you are unable to join in person, but would like to follow along, you
can join virtually via zoom:
https://stanford.zoom.us/j/93456697960?pwd=TXJqU1hpV09tL2E1NDViMHVsblBGUT09

Cheers,
Moses

On Thu, Mar 17, 2022 at 12:03 PM Moses Charikar <moses at cs.stanford.edu>
wrote:

> 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 cs.stanford.edu>
> 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.
>>
>> https://arxiv.org/abs/2203.00671
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20220318/94adefe3/attachment.html>


More information about the theory-seminar mailing list