[Theory] Luncheon at noon on 5th floor: 7/16 Talks at TTIC: Janani Sundaresan, University of Waterloo

[Mary Marre via Theory]

*Hello All,*

*Please join the PRE-TALK Lunch at NOON with Janani Sundaresan at the 5th
Floor Commons!*

*Thank You!*

*Mary*

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 Wed, Jul 16, 2025 at 11:11 AM Mary Marre <mmarre at ttic.edu> wrote:

> *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 Tue, Jul 15, 2025 at 5:27 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> *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/20250716/4273e5d0/attachment.html>