[Theory] 7/16 Talks at TTIC: Janani Sundaresan, University of Waterloo

[Mary Marre via Theory]

*When*:    Wednesday, July 16, 2025 at* 12:30** pm** CT *

*Where*:   Talk will be given *live, in-person* at
               TTIC, 6045 S. Kenwood Avenue
               5th Floor, *Room 530*

*Virtually*: via Panopto (livestream
<https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=fe96312e-49de-41e8-9acd-b317011ca545>
)

*Who:  *    Janani Sundaresan, University of Waterloo


*Title:* Distributed Triangle Detection is Hard in Few Rounds
*Abstract:* In the CONGEST model, $n$ 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 $O(\log n)$. We prove that detecting a triangle in this model
requires $\Omega(\log \log n)$ rounds.
Prior to our work, the only lower bound was that at least two rounds are
necessary.

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.

Joint work with Sepehr Assadi (https://arxiv.org/abs/2504.01802).

*Host: *Santhoshini Velusamy



Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue, Rm 517*
*Chicago, IL  60637*
*773-834-1757*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250711/024abbc2/attachment.html>