How much communication is required to determine whether a distributed graph is connected? We study the randomized two-party communication complexity of Graph Connectivity, where the edges of an n-vertex graph are distributed between Alice and Bob, and the goal is to decide whether the union of their edges forms a connected graph.
A classic result of Hajnal, Maass, and Turán (STOC '88) shows that deterministic protocols require $\Omega(n \log n)$ bits, even with unlimited rounds of interaction. In contrast, for randomized protocols with unbounded rounds, the best known lower bound via a reduction from Set Disjointness due to Babai, Frankl, and Simon (FOCS '86) is only $\Omega(n)$. Closing this gap has remained a long-standing open problem, recently highlighted for its algorithmic significance by Apers et al. (FOCS '22). In this talk, we show that any randomized two-round protocol for Graph Connectivity must communicate $\Omega(n \log n)$ bits, matching the deterministic upper bound in this bounded-round setting. Our proof is based on a reduction from a restricted form of the Pointer Chasing problem, originally studied by Papadimitriou and Sipser (JCSS '84). Our reduction also allows us to obtain $\omega(n)$ lower bounds for any constant number of rounds, by extending deterministic pointer-chasing bounds in prior work by Ponzio, Radhakrishnan, and Venkatesh (JCSS '01) to the randomized setting. This is joint work with Jaikumar Radhakrishnan (ICTS-TIFR, Bengaluru) and Chaitanya Reddy (IIT Hyderabad).
Short Bio: Rakesh Venkat is a faculty member at the Indian Institute of Technology Hyderabad. He received his Ph.D. from the Tata Institute of Fundamental Research (TIFR), Mumbai. His research interests lie in approximation algorithms and computational complexity theory.
