[Theory] [Theory Lunch] Tarun Kathuria, Wednesday 3/9 12:30pm-1:30pm, JCL 390.

[Adela DePavia]

Date: March 9th, Wednesday
Time: 12:30pm CT
Location: JCL 390

Speaker:  Tarun Kathuria

Title: An O(m^{4/3+o(1)) Algorithm for Max Flow on Unit Capacity Graphs

Zoom: [link<https://uchicago.zoom.us/j/93576083259?pwd=L2Vhb2VJYjRvTjRLM09YSkYzMjVMQT09>]

Abstract: In this talk, I’ll talk about an interior point method, inspired by potential reduction methods, for the maximum flow problem. I’ll first show how to recover the O(\sqrt{m}) iteration algorithm while ensuring progress dependent only on the \infty norm of the congestion of the flow, which was the main bottleneck of previous approaches. Then, I’ll show how to combine it with weight perturbation strategies of Madry and improvements by Liu and Sidford using \ell_2-\ell_p flows to get the desired iteration complexity of O(m^{1/3+o(1)}) for unit capacity graphs. Based on work by myself and independently obtained by Liu and Sidford.

COVID Policy Update: As per university policy, masking is not currently required for in-person attendance. Please note that we will have fully masked and social-distanced tables available to accommodate any attendees who would prefer such arrangements. Please contact us if you have any questions or feedback.

[Theory Lunch Webpage<https://orecchia.net/talk/an-o%5Cleft-m4/3-o1%5Cright-algorithm-for-max-flow-on-unit-capacity-graphs/>]
[Theory Lunch Calendar<https://orecchia.net/event/>]

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20220307/6be4c2f7/attachment.html>