TCS+ talk: Wednesday, October 8, Janani Sundaresan, University of Waterloo
Clement Canonne
Our first talk of the season will take place on Wednesday, October 8th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Janani Sundaresan from University of Waterloo will speak about "Distributed Triangle Detection is Hard in Few Rounds" (abstract below).
Please sign up on the online form at https://sites.google.com/view/tcsplus/welcome/next-tcs-talk if you wish to join the talk as an individual or a group. Registration is /not/ required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The link to the recording will also be posted on our website afterwards.)
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)