<div dir="ltr"><div dir="ltr"><div><div class="gmail_default" style="font-size:small"><font style="font-family:arial,sans-serif;color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b> </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font style="font-family:arial,sans-serif;color:rgb(0,0,0)"> Wednes</font><span class="gmail_default" style="font-family:arial,sans-serif;color:rgb(0,0,0)">day, April 16,<span class="gmail_default"> </span>2025</span><font style="font-family:arial,sans-serif;color:rgb(0,0,0)"> at</font><b><font color="#000000" style="font-family:arial,sans-serif"> <u style="background-color:rgb(255,255,0)">11:00</u></font></b><font color="#000000"><u><b><font face="arial, sans-serif"><span style="background-color:rgb(255,255,0)"> am</span></font></b><b style="background-color:rgb(255,255,0)"><font face="arial, sans-serif"> CT </font></b></u></font></font></font></div><div><div class="gmail_default"><div class="gmail_default"><div class="gmail_default"><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><b><font color="#500050" face="arial, sans-serif"><br></font></b></p><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><b><font color="#500050">Where: </font></b><font color="#000000">Talk will be given </font><font color="#000000" style="font-weight:bold"><u>live, in-person</u></font><font style="font-weight:bold"> </font>at<br></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font color="#500050"> </font><font color="#000000"> TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> 5th Floor, Room 530<b> </b></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b><span style="color:black"><br></span></b></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><b style="font-family:arial,sans-serif;color:rgb(60,64,67);letter-spacing:0.2px">Virtually:</b><span style="font-family:arial,sans-serif;color:rgb(60,64,67);letter-spacing:0.2px"> </span><span style="letter-spacing:0.2px"><font color="#0000ff" face="tahoma, sans-serif"><b> </b></font></span><span style="font-family:arial,sans-serif;letter-spacing:0.2px"><font color="#3c4043"> </font></span><i style="font-family:arial,sans-serif;letter-spacing:0.2px"><font color="#000000">livestream via </font><b style="color:rgb(0,0,255)"><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=25343c36-0bba-4d24-b07e-b2ba017629ff" target="_blank">panopto</a></b></i></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><span style="letter-spacing:0.2px"><b style="font-style:italic;font-family:arial,sans-serif;color:rgb(0,0,255)"> </b></span><b style="letter-spacing:0.2px"><font size="1" face="tahoma, sans-serif"> </font></b><b style="color:rgb(60,64,67);letter-spacing:0.2px"><font face="arial, sans-serif"> </font></b></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="color:rgb(80,0,80);vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b> <font color="#500050"> </font><font color="#000000"><font color="#500050"> </font></font></font></font></font>Vihan Shah, University of Waterloo</p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><div style="border-top:none;border-right:none;border-left:none;border-bottom:2.25pt solid rgb(11,118,159);padding:0in 0in 1pt"></div><div><br></div></div></div><div class="gmail_default"><div dir="ltr"><p dir="ltr" id="m_4637356163276351851m_-2834646526354896859m_-3504761229940322681m_4938701260463822682m_5860868498644129419m_-8505693634201348731m_-8109962251780210301m_2767765040961654113m_4331931867628220036m_-4442932724059632450gmail-docs-internal-guid-5f578bda-7fff-41e8-2cfc-0aaba7b02842" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font face="arial, sans-serif"><b style="color:rgb(31,31,31)">Title</b><span style="color:rgb(31,31,31)">: Space Complexity of Minimum Cut Problems in Single-Pass Streams</span><br style="color:rgb(31,31,31)"><span style="color:rgb(31,31,31)"> </span><br style="color:rgb(31,31,31)"><b style="color:rgb(31,31,31)">Abstract</b><span style="color:rgb(31,31,31)">: We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. Since finding the exact minimum cut essentially requires you to store the entire stream, we study the (1+eps)-approximate minimum cut problem. An upper bound for streaming (1+eps)-approximate minimum cut easily follows from streaming (1+eps) cut sparsification which is a very well-studied problem. It has an upper bound using O(n polylog n / eps^2) space [AG09] and a lower bound of Omega(n/eps^2) bits [CKST19]. This immediately provides an upper bound of O(n polylog n / eps^2) bits for streaming (1+eps)-approximate minimum cut, but the lower bound does not carry over. The best lower bound for (1+eps)-approximate minimum cut is Omega(n log 1/eps) bits [AG09]. This raises the fundamental question, what is the streaming space complexity of (1+eps)-approximate minimum cut?</span></font></p><p dir="ltr" id="m_4637356163276351851m_-2834646526354896859m_-3504761229940322681m_4938701260463822682m_5860868498644129419m_-8505693634201348731m_-8109962251780210301m_2767765040961654113m_4331931867628220036m_-4442932724059632450gmail-docs-internal-guid-5f578bda-7fff-41e8-2cfc-0aaba7b02842" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font face="arial, sans-serif"><br style="color:rgb(31,31,31)"><span style="color:rgb(31,31,31)">In our paper we resolve this question up to polylogarithmic factors. Additionally, we explore the random-order streaming model, a relaxation of the adversarial streaming model, and demonstrate that significantly better bounds can be achieved in this setting.</span><br style="color:rgb(31,31,31)"><br style="color:rgb(31,31,31)"><b style="color:rgb(31,31,31)">Bio</b><span style="color:rgb(31,31,31)">: My research interest is in Theoretical Computer Science and specifically in Streaming Algorithms. I have recently also worked on Sublinear, Dynamic, and Learning-Augmented algorithms. I generally enjoy working on Graph problems in these settings.</span></font></p><font size="2" face="arial, sans-serif"><br></font></div></div></div></div><div><div class="gmail_default"><font face="arial, sans-serif"><b>Host: </b><a href="mailto:vakilian@ttic.edu" rel="noreferrer" target="_blank"><b>Ali Vakilian</b></a></font></div></div><br class="gmail-Apple-interchange-newline"><br clear="all"></div><div><br></div><div><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue, Rm 517</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i><br></font></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote gmail_quote_container"><div dir="ltr" class="gmail_attr">On Wed, Apr 16, 2025 at 9:46 AM Mary Marre <<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div><div style="font-size:small"><font style="font-family:arial,sans-serif;color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b> </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font style="font-family:arial,sans-serif;color:rgb(0,0,0)"> Wednes</font><span class="gmail_default" style="font-family:arial,sans-serif;color:rgb(0,0,0)">day, April 16,<span class="gmail_default"> </span>2025</span><font style="font-family:arial,sans-serif;color:rgb(0,0,0)"> at</font><b><font color="#000000" style="font-family:arial,sans-serif"> <u style="background-color:rgb(255,255,0)">11:00</u></font></b><font color="#000000"><u><b><font face="arial, sans-serif"><span style="background-color:rgb(255,255,0)"> am</span></font></b><b style="background-color:rgb(255,255,0)"><font face="arial, sans-serif"> CT </font></b></u></font></font></font></div><div><div><div><div><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><b><font color="#500050" face="arial, sans-serif"><br></font></b></p><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><b><font color="#500050">Where: </font></b><font color="#000000">Talk will be given </font><font color="#000000" style="font-weight:bold"><u>live, in-person</u></font><font style="font-weight:bold"> </font>at<br></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font color="#500050"> </font><font color="#000000"> TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> 5th Floor, Room 530<b> </b></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b><span style="color:black"><br></span></b></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><b style="font-family:arial,sans-serif;color:rgb(60,64,67);letter-spacing:0.2px">Virtually:</b><span style="font-family:arial,sans-serif;color:rgb(60,64,67);letter-spacing:0.2px"> </span><span style="letter-spacing:0.2px"><font color="#0000ff" face="tahoma, sans-serif"><b> </b></font></span><span style="font-family:arial,sans-serif;letter-spacing:0.2px"><font color="#3c4043"> </font></span><i style="font-family:arial,sans-serif;letter-spacing:0.2px"><font color="#000000">livestream via </font><b style="color:rgb(0,0,255)"><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=25343c36-0bba-4d24-b07e-b2ba017629ff" target="_blank">panopto</a></b></i></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><span style="letter-spacing:0.2px"><b style="font-style:italic;font-family:arial,sans-serif;color:rgb(0,0,255)"> </b></span><b style="letter-spacing:0.2px"><font size="1" face="tahoma, sans-serif"> </font></b><b style="color:rgb(60,64,67);letter-spacing:0.2px"><font face="arial, sans-serif"> </font></b></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="color:rgb(80,0,80);vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b> <font color="#500050"> </font><font color="#000000"><font color="#500050"> </font></font></font></font></font>Vihan Shah, University of Waterloo</p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><div style="border-top:none;border-right:none;border-left:none;border-bottom:2.25pt solid rgb(11,118,159);padding:0in 0in 1pt"></div><div><br></div></div></div><div><div dir="ltr"><p dir="ltr" id="m_4637356163276351851m_-2834646526354896859m_-3504761229940322681m_4938701260463822682m_5860868498644129419m_-8505693634201348731m_-8109962251780210301m_2767765040961654113m_4331931867628220036m_-4442932724059632450gmail-docs-internal-guid-5f578bda-7fff-41e8-2cfc-0aaba7b02842" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font face="arial, sans-serif"><b style="color:rgb(31,31,31)">Title</b><span style="color:rgb(31,31,31)">: Space Complexity of Minimum Cut Problems in Single-Pass Streams</span><br style="color:rgb(31,31,31)"><span style="color:rgb(31,31,31)"> </span><br style="color:rgb(31,31,31)"><b style="color:rgb(31,31,31)">Abstract</b><span style="color:rgb(31,31,31)">: We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. Since finding the exact minimum cut essentially requires you to store the entire stream, we study the (1+eps)-approximate minimum cut problem. An upper bound for streaming (1+eps)-approximate minimum cut easily follows from streaming (1+eps) cut sparsification which is a very well-studied problem. It has an upper bound using O(n polylog n / eps^2) space [AG09] and a lower bound of Omega(n/eps^2) bits [CKST19]. This immediately provides an upper bound of O(n polylog n / eps^2) bits for streaming (1+eps)-approximate minimum cut, but the lower bound does not carry over. The best lower bound for (1+eps)-approximate minimum cut is Omega(n log 1/eps) bits [AG09]. This raises the fundamental question, what is the streaming space complexity of (1+eps)-approximate minimum cut?</span></font></p><p dir="ltr" id="m_4637356163276351851m_-2834646526354896859m_-3504761229940322681m_4938701260463822682m_5860868498644129419m_-8505693634201348731m_-8109962251780210301m_2767765040961654113m_4331931867628220036m_-4442932724059632450gmail-docs-internal-guid-5f578bda-7fff-41e8-2cfc-0aaba7b02842" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font face="arial, sans-serif"><br style="color:rgb(31,31,31)"><span style="color:rgb(31,31,31)">In our paper we resolve this question up to polylogarithmic factors. Additionally, we explore the random-order streaming model, a relaxation of the adversarial streaming model, and demonstrate that significantly better bounds can be achieved in this setting.</span><br style="color:rgb(31,31,31)"><br style="color:rgb(31,31,31)"><b style="color:rgb(31,31,31)">Bio</b><span style="color:rgb(31,31,31)">: My research interest is in Theoretical Computer Science and specifically in Streaming Algorithms. I have recently also worked on Sublinear, Dynamic, and Learning-Augmented algorithms. I generally enjoy working on Graph problems in these settings.</span></font></p><font size="2" face="arial, sans-serif"><br></font></div></div></div></div><div><div><font face="arial, sans-serif"><b>Host: </b><a href="mailto:vakilian@ttic.edu" rel="noreferrer" target="_blank"><b>Ali Vakilian</b></a></font></div></div><br><br clear="all"></div><div><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue, Rm 517</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i><br></font></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Apr 15, 2025 at 2:44 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div><div style="font-size:small"><font style="font-family:arial,sans-serif;color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b> </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font style="font-family:arial,sans-serif;color:rgb(0,0,0)"> Wednes</font><span class="gmail_default" style="font-family:arial,sans-serif;color:rgb(0,0,0)">day, April 16,<span class="gmail_default"> </span>2025</span><font style="font-family:arial,sans-serif;color:rgb(0,0,0)"> at</font><b><font color="#000000" style="font-family:arial,sans-serif"> <u style="background-color:rgb(255,255,0)">11:00</u></font></b><font color="#000000"><u><b><font face="arial, sans-serif"><span style="background-color:rgb(255,255,0)"> am</span></font></b><b style="background-color:rgb(255,255,0)"><font face="arial, sans-serif"> CT </font></b></u></font></font></font></div><div><div><div><div><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><b><font color="#500050" face="arial, sans-serif"><br></font></b></p><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><b><font color="#500050">Where: </font></b><font color="#000000">Talk will be given </font><font color="#000000" style="font-weight:bold"><u>live, in-person</u></font><font style="font-weight:bold"> </font>at<br></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font color="#500050"> </font><font color="#000000"> TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> 5th Floor, Room 530<b> </b></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b><span style="color:black"><br></span></b></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><b style="font-family:arial,sans-serif;color:rgb(60,64,67);letter-spacing:0.2px">Virtually:</b><span style="font-family:arial,sans-serif;color:rgb(60,64,67);letter-spacing:0.2px"> </span><span style="letter-spacing:0.2px"><font color="#0000ff" face="tahoma, sans-serif"><b> </b></font></span><span style="font-family:arial,sans-serif;letter-spacing:0.2px"><font color="#3c4043"> </font></span><i style="font-family:arial,sans-serif;letter-spacing:0.2px"><font color="#000000">livestream via </font><b style="color:rgb(0,0,255)"><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=25343c36-0bba-4d24-b07e-b2ba017629ff" target="_blank">panopto</a></b></i></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><span style="letter-spacing:0.2px"><b style="font-style:italic;font-family:arial,sans-serif;color:rgb(0,0,255)"> </b></span><b style="letter-spacing:0.2px"><font size="1" face="tahoma, sans-serif"> </font></b><b style="color:rgb(60,64,67);letter-spacing:0.2px"><font face="arial, sans-serif"> </font></b></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="color:rgb(80,0,80);vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b> <font color="#500050"> </font><font color="#000000"><font color="#500050"> </font></font></font></font></font>Vihan Shah, University of Waterloo</p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><div style="border-top:none;border-right:none;border-left:none;border-bottom:2.25pt solid rgb(11,118,159);padding:0in 0in 1pt"></div><div><br></div></div></div><div><div dir="ltr"><p dir="ltr" id="m_4637356163276351851m_-2834646526354896859m_-3504761229940322681m_4938701260463822682m_5860868498644129419m_-8505693634201348731m_-8109962251780210301m_2767765040961654113m_4331931867628220036m_-4442932724059632450gmail-docs-internal-guid-5f578bda-7fff-41e8-2cfc-0aaba7b02842" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font face="arial, sans-serif"><b style="color:rgb(31,31,31)">Title</b><span style="color:rgb(31,31,31)">: Space Complexity of Minimum Cut Problems in Single-Pass Streams</span><br style="color:rgb(31,31,31)"><span style="color:rgb(31,31,31)"> </span><br style="color:rgb(31,31,31)"><b style="color:rgb(31,31,31)">Abstract</b><span style="color:rgb(31,31,31)">: We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. Since finding the exact minimum cut essentially requires you to store the entire stream, we study the (1+eps)-approximate minimum cut problem. An upper bound for streaming (1+eps)-approximate minimum cut easily follows from streaming (1+eps) cut sparsification which is a very well-studied problem. It has an upper bound using O(n polylog n / eps^2) space [AG09] and a lower bound of Omega(n/eps^2) bits [CKST19]. This immediately provides an upper bound of O(n polylog n / eps^2) bits for streaming (1+eps)-approximate minimum cut, but the lower bound does not carry over. The best lower bound for (1+eps)-approximate minimum cut is Omega(n log 1/eps) bits [AG09]. This raises the fundamental question, what is the streaming space complexity of (1+eps)-approximate minimum cut?</span></font></p><p dir="ltr" id="m_4637356163276351851m_-2834646526354896859m_-3504761229940322681m_4938701260463822682m_5860868498644129419m_-8505693634201348731m_-8109962251780210301m_2767765040961654113m_4331931867628220036m_-4442932724059632450gmail-docs-internal-guid-5f578bda-7fff-41e8-2cfc-0aaba7b02842" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font face="arial, sans-serif"><br style="color:rgb(31,31,31)"><span style="color:rgb(31,31,31)">In our paper we resolve this question up to polylogarithmic factors. Additionally, we explore the random-order streaming model, a relaxation of the adversarial streaming model, and demonstrate that significantly better bounds can be achieved in this setting.</span><br style="color:rgb(31,31,31)"><br style="color:rgb(31,31,31)"><b style="color:rgb(31,31,31)">Bio</b><span style="color:rgb(31,31,31)">: My research interest is in Theoretical Computer Science and specifically in Streaming Algorithms. I have recently also worked on Sublinear, Dynamic, and Learning-Augmented algorithms. I generally enjoy working on Graph problems in these settings.</span></font></p><font size="2" face="arial, sans-serif"><br></font></div></div></div></div><div><div><font face="arial, sans-serif"><b>Host: </b><a href="mailto:vakilian@ttic.edu" rel="noreferrer" target="_blank"><b>Ali Vakilian</b></a></font></div></div><br><br clear="all"></div><div><br></div><div><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue, Rm 517</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i><br></font></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Apr 9, 2025 at 7:28 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div><div style="font-size:small"><font style="font-family:arial,sans-serif;color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b> </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font style="font-family:arial,sans-serif;color:rgb(0,0,0)"> Wednes</font><span class="gmail_default" style="font-family:arial,sans-serif;color:rgb(0,0,0)">day, April 16,<span class="gmail_default"> </span>2025</span><font style="font-family:arial,sans-serif;color:rgb(0,0,0)"> at</font><b><font color="#000000" style="font-family:arial,sans-serif"> <u style="background-color:rgb(255,255,0)">11:00</u></font></b><font color="#000000"><u><b><font face="arial, sans-serif"><span style="background-color:rgb(255,255,0)"> am</span></font></b><b style="background-color:rgb(255,255,0)"><font face="arial, sans-serif"> CT </font></b></u></font></font></font></div><div><div><div><div><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><b><font color="#500050" face="arial, sans-serif"><br></font></b></p><p style="color:rgb(80,0,80);font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><b><font color="#500050">Where: </font></b><font color="#000000">Talk will be given </font><font color="#000000" style="font-weight:bold"><u>live, in-person</u></font><font style="font-weight:bold"> </font>at<br></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font color="#500050"> </font><font color="#000000"> TTIC, 6045 S. Kenwood Avenue</font></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> 5th Floor, Room 530<b> </b></font></p><p class="MsoNormal" style="margin:0in;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b><span style="color:black"><br></span></b></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><b style="font-family:arial,sans-serif;color:rgb(60,64,67);letter-spacing:0.2px">Virtually:</b><span style="font-family:arial,sans-serif;color:rgb(60,64,67);letter-spacing:0.2px"> </span><span style="letter-spacing:0.2px"><font color="#0000ff" face="tahoma, sans-serif"><b> </b></font></span><span style="font-family:arial,sans-serif;letter-spacing:0.2px"><font color="#3c4043"> </font></span><i style="font-family:arial,sans-serif;letter-spacing:0.2px"><font color="#000000">livestream via </font><b style="color:rgb(0,0,255)"><a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=25343c36-0bba-4d24-b07e-b2ba017629ff" target="_blank">panopto</a></b></i></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><span style="letter-spacing:0.2px"><b style="font-style:italic;font-family:arial,sans-serif;color:rgb(0,0,255)"> </b></span><b style="letter-spacing:0.2px"><font size="1" face="tahoma, sans-serif"> </font></b><b style="color:rgb(60,64,67);letter-spacing:0.2px"><font face="arial, sans-serif"> </font></b></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="color:rgb(80,0,80);vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b> <font color="#500050"> </font><font color="#000000"><font color="#500050"> </font></font></font></font></font>Vihan Shah, University of Waterloo</p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><div style="border-top:none;border-right:none;border-left:none;border-bottom:2.25pt solid rgb(11,118,159);padding:0in 0in 1pt"></div><div><br></div></div></div><div><div dir="ltr"><p dir="ltr" id="m_4637356163276351851m_-2834646526354896859m_-3504761229940322681m_4938701260463822682m_5860868498644129419m_-8505693634201348731m_-8109962251780210301m_2767765040961654113m_4331931867628220036m_-4442932724059632450gmail-docs-internal-guid-5f578bda-7fff-41e8-2cfc-0aaba7b02842" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="background-color:rgb(255,255,255)"><font face="arial, sans-serif"><b style="color:rgb(31,31,31)">Title</b><span style="color:rgb(31,31,31)">: Space Complexity of Minimum Cut Problems in Single-Pass Streams</span><br style="color:rgb(31,31,31)"><span style="color:rgb(31,31,31)"> </span><br style="color:rgb(31,31,31)"><b style="color:rgb(31,31,31)">Abstract</b><span style="color:rgb(31,31,31)">: We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. Since finding the exact minimum cut essentially requires you to store the entire stream, we study the (1+eps)-approximate minimum cut problem. An upper bound for streaming (1+eps)-approximate minimum cut easily follows from streaming (1+eps) cut sparsification which is a very well-studied problem. It has an upper bound using O(n polylog n / eps^2) space [AG09] and a lower bound of Omega(n/eps^2) bits [CKST19]. This immediately provides an upper bound of O(n polylog n / eps^2) bits for streaming (1+eps)-approximate minimum cut, but the lower bound does not carry over. The best lower bound for (1+eps)-approximate minimum cut is Omega(n log 1/eps) bits [AG09]. This raises the fundamental question, what is the streaming space complexity of (1+eps)-approximate minimum cut?</span></font></span></p><p dir="ltr" id="m_4637356163276351851m_-2834646526354896859m_-3504761229940322681m_4938701260463822682m_5860868498644129419m_-8505693634201348731m_-8109962251780210301m_2767765040961654113m_4331931867628220036m_-4442932724059632450gmail-docs-internal-guid-5f578bda-7fff-41e8-2cfc-0aaba7b02842" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="background-color:rgb(255,255,255)"><font face="arial, sans-serif"><br style="color:rgb(31,31,31)"><span style="color:rgb(31,31,31)">In our paper we resolve this question up to polylogarithmic factors. Additionally, we explore the random-order streaming model, a relaxation of the adversarial streaming model, and demonstrate that significantly better bounds can be achieved in this setting.</span><br style="color:rgb(31,31,31)"><br style="color:rgb(31,31,31)"><b style="color:rgb(31,31,31)">Bio</b><span style="color:rgb(31,31,31)">: My research interest is in Theoretical Computer Science and specifically in Streaming Algorithms. I have recently also worked on Sublinear, Dynamic, and Learning-Augmented algorithms. I generally enjoy working on Graph problems in these settings.</span></font></span></p><font size="2" face="arial, sans-serif"><br></font></div></div></div></div><div><div><font face="arial, sans-serif"><b>Host: </b><a href="mailto:vakilian@ttic.edu" rel="noreferrer" target="_blank"><b>Ali Vakilian</b></a></font></div></div><div><font face="arial, sans-serif"><br></font></div></div><div><br></div><div><br></div><div><br></div><div><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue, Rm 517</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i><br></font></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div>
</div>
</blockquote></div></div>
</blockquote></div></div>
</blockquote></div></div>