Optimal Two-Round Communication Lower Bound for Graph Connectivity via Pointer Chasing

Title of the Talk: Optimal Two-Round Communication Lower Bound for Graph Connectivity via Pointer Chasing
Speakers: Chaitanya Reddy
Host Faculty: Dr.Nitin Saurabh
Date: Jan 07, 2026
Time: 12:00pm
Venue: CSE-LH-02

Abstract: We study the communication complexity of the graph connectivity problem, where the edges of an n-vertex undirected graph are distributed between two players, Alice and Bob. We focus on the total number of bits that must be exchanged between the players to determine if the graph is connected. For deterministic protocols, the communication complexity is known to be Theta(n log n), a result established by Hajnal, Maass, and Turan (1988). This matches the simple upper bound where Alice sends a spanning forest of her edges to Bob. While an Omega(n log n) lower bound for one-round randomized protocols was shown by Sun and Woodruff in 2015, the best-known randomized lower bound for multi-round protocols remained Omega(n), following a reduction from set disjointness by Babai, Frankl, and Simon (1986). Closing the gap between this lower bound and the O(n log n) upper bound has remained a major open question.

In this talk, we show an optimal Omega(n log n) lower bound for randomized two-round protocols, via a reduction from a restricted version of the pointer chasing problem. Our proof develops lower bound techniques for the bit-version of pointer chasing that avoid round dependent sequential pointer fixing; instead, our analysis allows them to vary, which is essential for handling protocols where players communicate Omega(n log n) bits. Our result demonstrates that the simple spanning forest protocol remains optimal even when the players are allowed two rounds of randomized communication.

This is joint work with Jaikumar Radhakrishnan and Rakesh Venkat, to appear in ITCS’26.

Bio: Chaitanya Reddy is a PhD student in the CSE department at IITH.