| Title | : | Distributed Triangle Detection is Hard in Few Rounds |
| Speaker | : | Janani Sundaresan (University of Waterloo) |
| Details | : | Tue, Sep 9, 2025 4:00 PM, @ SSB 334 |
| 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) |