<div dir="ltr"><div><div class="gmail_default" 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 class="gmail_default"><div class="gmail_default"><div><b><br></b></div><div><b>Where</b>:   <span class="gmail-il">Talk</span> will be given <b><font color="#0000ff">live, in-person</font></b> at<br>               <span class="gmail-il">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 class="gmail_default">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">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" data-smartmail="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>