<div dir="ltr"><div dir="ltr"><div><div class="gmail_default"><b><font face="georgia, serif">Hello All,</font></b></div><div class="gmail_default"><b><font face="georgia, serif"><br></font></b></div><div class="gmail_default"><b><font face="georgia, serif">Please join the PRE-TALK <span style="background-color:rgb(255,255,0)">Lunch at NOON</span> with Janani Sundaresan at the <u>5th Floor Commons</u>!</font></b></div><div class="gmail_default"><b><font face="georgia, serif"><br></font></b></div><div class="gmail_default"><b><font face="georgia, serif">Thank You!</font></b></div><div class="gmail_default"><b><font face="georgia, serif"><br></font></b></div><div class="gmail_default"><b><font face="georgia, serif">Mary</font></b></div><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 gmail_quote_container"><div dir="ltr" class="gmail_attr">On Wed, Jul 16, 2025 at 11:11 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"><b>When</b>:    Wednes<span class="gmail_default" style="font-family:arial,sans-serif;color:rgb(0,0,0)">day, July 16<span class="gmail_default">, </span>2025</span><font style="font-family:arial,sans-serif;color:rgb(0,0,0)"> at</font><b style="font-family:arial,sans-serif;color:rgb(0,0,0)"> <span style="background-color:rgb(255,255,0)"><u>12:30</u></span></b><span style="color:rgb(80,0,80);font-family:arial,sans-serif;background-color:rgb(255,255,0)"><b><u><font color="#000000"> pm</font></u></b><b><u><font color="#000000"> CT</font></u><font color="#000000"> </font></b></span></div><div>    <i><font face="arial, sans-serif">  </font><font face="georgia, serif">         <span style="background-color:rgb(255,255,0);color:rgb(0,0,0)">(Food will be provided at 12:00 pm ~ 5th floor Commons)</span></font></i></div><div><div><div><div><b><br></b></div><div><b>Where</b>:   Talk will be given <b><font color="#0000ff">live, in-person</font></b> at<br>               TTIC, 6045 S. Kenwood Avenue<br>               5th Floor, <b><u><font color="#000000">Room 530</font></u></b></div><div><br><b>Virtually</b>: via Panopto (<a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=fe96312e-49de-41e8-9acd-b317011ca545" target="_blank">livestream</a>)<br></div><div>                 </div><div><b>Who:  </b>    Janani Sundaresan, University of Waterloo</div><div><br></div><div><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><p class="MsoNormal" style="margin:0in 0in 8pt;font-size:11pt;text-align:justify;line-height:15.6933px;font-family:Aptos,sans-serif"><b style="font-family:Arial,Helvetica,sans-serif;font-size:small"><br></b></p><p class="MsoNormal" style="margin:0in 0in 8pt;font-size:11pt;text-align:justify;line-height:15.6933px;font-family:Aptos,sans-serif"><b style="font-family:Arial,Helvetica,sans-serif;font-size:small">Title:</b><span style="font-family:Arial,Helvetica,sans-serif;font-size:small"> Distributed Triangle Detection is Hard in Few Rounds</span></p></div></div><b>Abstract:</b> In the CONGEST model, <span style="color:rgb(0,0,0);font-family:Aptos,Aptos_EmbeddedFont,Aptos_MSFontService,Calibri,Helvetica,sans-serif;font-size:16px">$n$</span> vertices with information only about their neighborhoods are allowed to communicate to each other over the edges of the input graph. Communication happens in synchronous rounds with a bandwidth of <span style="color:rgb(0,0,0);font-family:Aptos,Aptos_EmbeddedFont,Aptos_MSFontService,Calibri,Helvetica,sans-serif;font-size:16px">$</span>O(\log n)<span style="color:rgb(0,0,0);font-family:Aptos,Aptos_EmbeddedFont,Aptos_MSFontService,Calibri,Helvetica,sans-serif;font-size:16px">$</span>. We prove that detecting a triangle in this model requires <span style="color:rgb(0,0,0);font-family:Aptos,Aptos_EmbeddedFont,Aptos_MSFontService,Calibri,Helvetica,sans-serif;font-size:16px">$</span>\Omega(\log \log n)<span style="color:rgb(0,0,0);font-family:Aptos,Aptos_EmbeddedFont,Aptos_MSFontService,Calibri,Helvetica,sans-serif;font-size:16px">$</span> rounds.</div><div>Prior to our work, the only lower bound was that at least two rounds are necessary.<br><br>It is known that standard communication complexity arguments that have been used to get lower bounds in the CONGEST model in the past are incapable of giving any meaningful multi-round lower bounds for this problem. Our main contribution is a new information-theoretic technique that combines classical round elimination arguments of communication complexity with the point-to-point communication aspects of distributed networks and can be of independent interest.<br><br>Joint work with Sepehr Assadi (<a href="https://arxiv.org/abs/2504.01802" target="_blank">https://arxiv.org/abs/2504.01802</a>).<br><br><b>Host: </b>Santhoshini Velusamy</div></div><br clear="all"></div><div><br></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><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Jul 15, 2025 at 5:27 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"><b>When</b>:    Wednes<span class="gmail_default" style="font-family:arial,sans-serif;color:rgb(0,0,0)">day, July 16<span class="gmail_default">, </span>2025</span><font style="font-family:arial,sans-serif;color:rgb(0,0,0)"> at</font><b style="font-family:arial,sans-serif;color:rgb(0,0,0)"> <span style="background-color:rgb(255,255,0)"><u>12:30</u></span></b><span style="color:rgb(80,0,80);font-family:arial,sans-serif;background-color:rgb(255,255,0)"><b><u><font color="#000000"> pm</font></u></b><b><u><font color="#000000"> CT</font></u><font color="#000000"> </font></b></span></div><div>    <i><font face="arial, sans-serif">  </font><font face="georgia, serif">         <span style="background-color:rgb(255,255,0);color:rgb(0,0,0)">(Food will be provided at 12:00 pm ~ 5th floor Commons)</span></font></i></div><div><div><div><div><b><br></b></div><div><b>Where</b>:   <span>Talk</span> will be given <b><font color="#0000ff">live, in-person</font></b> at<br>               <span>TTIC</span>, 6045 S. Kenwood Avenue<br>               5th Floor, <b><u><font color="#000000">Room 530</font></u></b></div><div><br><b>Virtually</b>: via Panopto (<a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=fe96312e-49de-41e8-9acd-b317011ca545" target="_blank">livestream</a>)<br></div><div>                 </div><div><b>Who:  </b>    Janani Sundaresan, University of Waterloo</div><div><br></div><div><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><p class="MsoNormal" style="margin:0in 0in 8pt;font-size:11pt;text-align:justify;line-height:15.6933px;font-family:Aptos,sans-serif"><b style="font-family:Arial,Helvetica,sans-serif;font-size:small"><br></b></p><p class="MsoNormal" style="margin:0in 0in 8pt;font-size:11pt;text-align:justify;line-height:15.6933px;font-family:Aptos,sans-serif"><b style="font-family:Arial,Helvetica,sans-serif;font-size:small">Title:</b><span style="font-family:Arial,Helvetica,sans-serif;font-size:small"> Distributed Triangle Detection is Hard in Few Rounds</span></p></div></div><b>Abstract:</b> In the CONGEST model, <span style="color:rgb(0,0,0);font-family:Aptos,Aptos_EmbeddedFont,Aptos_MSFontService,Calibri,Helvetica,sans-serif;font-size:16px">$n$</span> vertices with information only about their neighborhoods are allowed to communicate to each other over the edges of the input graph. Communication happens in synchronous rounds with a bandwidth of <span style="color:rgb(0,0,0);font-family:Aptos,Aptos_EmbeddedFont,Aptos_MSFontService,Calibri,Helvetica,sans-serif;font-size:16px">$</span>O(\log n)<span style="color:rgb(0,0,0);font-family:Aptos,Aptos_EmbeddedFont,Aptos_MSFontService,Calibri,Helvetica,sans-serif;font-size:16px">$</span>. We prove that detecting a triangle in this model requires <span style="color:rgb(0,0,0);font-family:Aptos,Aptos_EmbeddedFont,Aptos_MSFontService,Calibri,Helvetica,sans-serif;font-size:16px">$</span>\Omega(\log \log n)<span style="color:rgb(0,0,0);font-family:Aptos,Aptos_EmbeddedFont,Aptos_MSFontService,Calibri,Helvetica,sans-serif;font-size:16px">$</span> rounds.</div><div>Prior to our work, the only lower bound was that at least two rounds are necessary.<br><br>It is known that standard communication complexity arguments that have been used to get lower bounds in the CONGEST model in the past are incapable of giving any meaningful multi-round lower bounds for this problem. Our main contribution is a new information-theoretic technique that combines classical round elimination arguments of communication complexity with the point-to-point communication aspects of distributed networks and can be of independent interest.<br><br>Joint work with Sepehr Assadi (<a href="https://arxiv.org/abs/2504.01802" target="_blank">https://arxiv.org/abs/2504.01802</a>).<br><br><b>Host: </b>Santhoshini Velusamy</div></div><div><br></div><div><br></div><div><br></div><div><br></div><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 Fri, Jul 11, 2025 at 12:26 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><div style="font-size:small"><b>When</b>:    Wednes<span class="gmail_default" style="font-family:arial,sans-serif;color:rgb(0,0,0)">day, July 16<span class="gmail_default">, </span>2025</span><font style="font-family:arial,sans-serif;color:rgb(0,0,0)"> at</font><b style="font-family:arial,sans-serif;color:rgb(0,0,0)"> <span style="background-color:rgb(255,255,0)"><u>12:30</u></span></b><span style="color:rgb(80,0,80);font-family:arial,sans-serif;background-color:rgb(255,255,0)"><b><u><font color="#000000"> pm</font></u></b><b><u><font color="#000000"> CT</font></u><font color="#000000"> </font></b></span></div><div><div><div><b><br></b></div><div><b>Where</b>:   <span>Talk</span> will be given <b><font color="#0000ff">live, in-person</font></b> at<br>               <span>TTIC</span>, 6045 S. Kenwood Avenue<br>               5th Floor, <b><u><font color="#000000">Room 530</font></u></b></div><div><br><b>Virtually</b>: via Panopto (<a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=fe96312e-49de-41e8-9acd-b317011ca545" target="_blank">livestream</a>)<br></div><div>                 </div><div><b>Who:  </b>    Janani Sundaresan, University of Waterloo</div><div><br></div><div><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><p class="MsoNormal" style="margin:0in 0in 8pt;font-size:11pt;text-align:justify;line-height:15.6933px;font-family:Aptos,sans-serif"><b style="font-family:Arial,Helvetica,sans-serif;font-size:small"><br></b></p><p class="MsoNormal" style="margin:0in 0in 8pt;font-size:11pt;text-align:justify;line-height:15.6933px;font-family:Aptos,sans-serif"><b style="font-family:Arial,Helvetica,sans-serif;font-size:small">Title:</b><span style="font-family:Arial,Helvetica,sans-serif;font-size:small"> Distributed Triangle Detection is Hard in Few Rounds</span></p></div></div><b>Abstract:</b> In the CONGEST model, <span style="color:rgb(0,0,0);font-family:Aptos,Aptos_EmbeddedFont,Aptos_MSFontService,Calibri,Helvetica,sans-serif;font-size:16px">$n$</span> vertices with information only about their neighborhoods are allowed to communicate to each other over the edges of the input graph. Communication happens in synchronous rounds with a bandwidth of <span style="color:rgb(0,0,0);font-family:Aptos,Aptos_EmbeddedFont,Aptos_MSFontService,Calibri,Helvetica,sans-serif;font-size:16px">$</span>O(\log n)<span style="color:rgb(0,0,0);font-family:Aptos,Aptos_EmbeddedFont,Aptos_MSFontService,Calibri,Helvetica,sans-serif;font-size:16px">$</span>. We prove that detecting a triangle in this model requires <span style="color:rgb(0,0,0);font-family:Aptos,Aptos_EmbeddedFont,Aptos_MSFontService,Calibri,Helvetica,sans-serif;font-size:16px">$</span>\Omega(\log \log n)<span style="color:rgb(0,0,0);font-family:Aptos,Aptos_EmbeddedFont,Aptos_MSFontService,Calibri,Helvetica,sans-serif;font-size:16px">$</span> rounds.</div><div>Prior to our work, the only lower bound was that at least two rounds are necessary.<br><br>It is known that standard communication complexity arguments that have been used to get lower bounds in the CONGEST model in the past are incapable of giving any meaningful multi-round lower bounds for this problem. Our main contribution is a new information-theoretic technique that combines classical round elimination arguments of communication complexity with the point-to-point communication aspects of distributed networks and can be of independent interest.<br><br>Joint work with Sepehr Assadi (<a href="https://arxiv.org/abs/2504.01802" target="_blank">https://arxiv.org/abs/2504.01802</a>).<br><br><b>Host: </b>Santhoshini Velusamy</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>
</blockquote></div></div>
</blockquote></div></div>
</blockquote></div></div>