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

[Mary Marre via Theory]

*When*:    Wednesday, July 16, 2025 at* 12:30** pm** CT *
    *           (Food will be provided at 12:00 pm ~ 5th floor Commons)*

*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>*


On Fri, Jul 11, 2025 at 12:26 PM Mary Marre <mmarre at ttic.edu> wrote:

> *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/20250715/676d2f6d/attachment.html>