TCS+ talk *this week*: Wednesday, October 8, Janani Sundaresan, University of Waterloo
Clement Canonne
This is a reminder that the next TCS+ talk (first of the season!) is taking place this week, Wednesday, October 8th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). The speakers' slides will be made available at https://sites.google.com/view/tcsplus/welcome/past-talks after the talk.
If you’d like to join the Zoom talk, please sign up using the form at https://sites.google.com/view/tcsplus/welcome/next-tcs-talk. The talk will also be recorded and posted shortly afterwards on our YouTube channel, here: http://www.youtube.com/user/TCSplusSeminars.
Hoping to see you all there,
The organizers
-------------------------------
Speaker: 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)
Clement Canonne
The link for tomorrow's TCS+ talk has been posted: you will be able to join tomorrow (Wednesday), starting at 12:50pm ET: https://berkeley.zoom.us/j/98954371813?pwd=V1hxN2Nrc2c5OEJFSWRqS29JeWM1dz09
(you will need a to be logged in on Zoom to join: a free account suffices)
Best,
-- Clément, on behalf of the TCS+ team
________________________________________
From: 'Clement Canonne' via TCS+ <tcsplus_...@googlegroups.com>
Sent: Monday, October 6, 2025 6:30 PM
To: TCS+ Announcement Mailing List
Subject: TCS+ talk *this week*: Wednesday, October 8, Janani Sundaresan, University of Waterloo
Hello everyone,
This is a reminder that the next TCS+ talk (first of the season!) is taking place this week, Wednesday, October 8th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). The speakers' slides will be made available at https://url.au.m.mimecastprotect.com/s/VbyBCOMKzVTZ53gvNiEfyuGT6_5?domain=sites.google.com after the talk.
If you’d like to join the Zoom talk, please sign up using the form at https://url.au.m.mimecastprotect.com/s/OwgwCP7LAXfNvQ230i0hvuxyL6g?domain=sites.google.com. The talk will also be recorded and posted shortly afterwards on our YouTube channel, here: https://url.au.m.mimecastprotect.com/s/M1pvCQnMBZflB7KoXTMiyuGAu2M?domain=youtube.com.
Hoping to see you all there,
The organizers
-------------------------------
Speaker: 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.
--
You received this message because you are subscribed to the Google Groups "TCS+" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tcsplus_announ...@googlegroups.com.
To view this discussion visit https://url.au.m.mimecastprotect.com/s/swhICVARKgCk0MEg2HQtKuEy9x6?domain=groups.google.com.
For more options, visit https://url.au.m.mimecastprotect.com/s/gzx7CWLVXkUXz0QD6fpuruoHAs9?domain=groups.google.com.