BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1258
DTSTAMP:20230914T125956Z
SUMMARY:Almost linear time algorithms for max-flow and more
DESCRIPTION:Speaker: Sushant Sachdeva (University of Toronto)\n\nAbstract: 
 \nWe give the first almost-linear time algorithm for computing exact maxim
 um flows and minimum-cost flows on directed graphs. By well known reductio
 ns\, this implies almost-linear time algorithms for several problems inclu
 ding bipartite matching\, optimal transport\, and undirected vertex connec
 tivity.\n\nOur algorithm is designed using a new Interior Point Method (IP
 M) that builds the flow as a sequence of almost-linear number of approxima
 te undirected minimum-ratio cycles\, each of which is computed and process
 ed very efficiently using a new dynamic data structure.\n\nOur framework e
 xtends to give an almost-linear time algorithm for computing flows that mi
 nimize general edge-separable convex functions to high accuracy. This give
 s the first almost-linear time algorithm for several problems including en
 tropy-regularized optimal transport\, matrix scaling\, p-norm flows\, and 
 Isotonic regression.\n\nJoint work with Li Chen\, Rasmus Kyng\, Yang Liu\,
  Richard Peng\, and Maximilian Probst Gutenberg.\n\nBio: Sushant Sachdeva 
 is a faculty member at the CS dept. at the University of Toronto and a Vec
 tor Institute affiliate. He is interested in algorithms\, and its connecti
 ons to optimization\, machine learning\, and statistics. His recent resear
 ch focus has been the design of fast algorithms for graph problems. https:
 //www.cs.toronto.edu/~sachdeva/\n
URL:https://www.tcs.tifr.res.in/web/events/1258
DTSTART;TZID=Asia/Kolkata:20221222T143000
DTEND;TZID=Asia/Kolkata:20221222T153000
LOCATION:A-201 and Zoom
END:VEVENT
END:VCALENDAR