<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div style="font-size: 12pt; color: rgb(0, 0, 0);">
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; margin: 0px; font-size: 15px; color: rgb(32, 31, 30); background-color: white;">
<span style="margin:0px"><span style="margin:0px;font-size:16px;color:rgb(49, 49, 49);word-spacing:1px"><font style="font-size:1.13em"><b>Date:</b> March 9th, Wednesday</font></span></span></div>
<div style="margin: 0px; font-size: 15px; color: rgb(32, 31, 30); background-color: white;">
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; margin: 0px;">
<div style="margin:0px;font-size:16px;color:rgb(49, 49, 49);word-spacing:1px"><font style="font-size:1.13em"><b>Time: </b>12:30pm CT</font></div>
<div style="margin:0px;font-size:16px;color:rgb(49, 49, 49);word-spacing:1px"><font style="font-size:1.13em"><b>Location: </b>JCL 390</font></div>
<div dir="auto" style="margin:0px;font-size:16px;color:rgb(49, 49, 49);word-spacing:1px">
<b><font style="font-size:1.13em"><br>
</font></b></div>
<div dir="auto" style="margin:0px;font-size:16px;color:rgb(49, 49, 49);word-spacing:1px">
<b><font style="font-size:1.13em">Speaker: Tarun Kathuria</font></b></div>
<div dir="auto" style="margin:0px;font-size:16px;color:rgb(49, 49, 49);word-spacing:1px">
<font size="4"><br>
</font></div>
<b style="color:rgb(49, 49, 49);font-size:16px;word-spacing:1px"><font style="font-size:1.13em">Title: </font></b><font size="4"><span style="font-family:"trebuchet ms", sans-serif;font-size:15px;background-color:rgb(255, 255, 255);display:inline !important">An
O(m^{4/3+o(1)) Algorithm for Max Flow on Unit Capacity Graphs</span></font></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; margin: 0px;"><b style="color:rgb(49, 49, 49);font-size:16px;word-spacing:1px"><font style="font-size:1.13em"><br>
</font></b></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; margin: 0px;"><span style="margin:0px;font-size:16px;color:rgb(49, 49, 49);word-spacing:1px"><font style="font-size:1.13em"><b>Zoom: </b>[<a href="https://uchicago.zoom.us/j/93576083259?pwd=L2Vhb2VJYjRvTjRLM09YSkYzMjVMQT09" title="https://uchicago.zoom.us/j/93576083259?pwd=L2Vhb2VJYjRvTjRLM09YSkYzMjVMQT09">link</a>]</font></span></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; margin: 0px;"><br>
</div>
<div style="margin: 0px;">
<div dir="auto" style="font-family: Calibri, Arial, Helvetica, sans-serif; margin: 0px;">
<font style="color:rgb(49, 49, 49);font-size:1.13em;word-spacing:1px"><b>Abstract: </b><span style="color:rgb(32, 31, 30);font-family:"trebuchet ms", sans-serif;font-size:15px;word-spacing:0px;background-color:rgb(255, 255, 255);display:inline !important">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.</span></font></div>
<div dir="auto" style="font-family: Calibri, Arial, Helvetica, sans-serif; margin: 0px;">
<font style="color:rgb(49, 49, 49);font-size:1.13em;word-spacing:1px"><span style="color:rgb(32, 31, 30);font-family:"trebuchet ms", sans-serif;font-size:15px;word-spacing:0px;background-color:rgb(255, 255, 255);display:inline !important"><br>
</span></font></div>
<div dir="auto" style="margin: 0px;"><font face="trebuchet ms, sans-serif"><b>COVID Policy Update:
</b>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. </font></div>
</div>
</div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; margin: 0px; font-size: 15px; color: rgb(32, 31, 30); background-color: white;">
<font size="4"><br>
</font></div>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; margin: 0px; font-size: 15px; color: rgb(32, 31, 30); background-color: white;">
<span style="margin:0px;font-size:large">[<a href="https://orecchia.net/talk/an-o%5Cleft-m4/3-o1%5Cright-algorithm-for-max-flow-on-unit-capacity-graphs/" title="https://orecchia.net/talk/an-o%5Cleft-m4/3-o1%5Cright-algorithm-for-max-flow-on-unit-capacity-graphs/">Theory Lunch Webpage</a>]<br>
[<a href="https://orecchia.net/event/" title="https://orecchia.net/event/"><span style="margin: 0px;"><span data-markjs="true" class="markgmtfzlfu6" data-ogac="" data-ogab="" data-ogsc="" data-ogsb="" style="margin:0px">Theory</span></span><span style="margin: 0px;"> </span><span style="margin: 0px;">Lunch</span><span style="margin: 0px;"> </span>Calendar</a>]</span></div>
<br>
</div>
</body>
</html>