BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1676
DTSTAMP:20260324T052011Z
SUMMARY:Optimal Two-Round Communication Lower bound for Graph Connectivity
DESCRIPTION:Speaker: Rakesh Venkat (Indian Institute of Technology Hyderaba
 d (IITH))\n\nAbstract: \nHow much communication is required to determine w
 hether 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 t
 o decide whether the union of their edges forms a connected graph.A classi
 c result of Hajnal\, Maass\, and Turán (STOC '88) shows that deterministi
 c protocols require $\\Omega(n \\log n)$ bits\, even with unlimited rounds
  of interaction. In contrast\, for randomized protocols with unbounded rou
 nds\, the best known lower bound via a reduction from Set Disjointness due
  to Babai\, Frankl\, and Simon (FOCS '86) is only $\\Omega(n)$. Closing th
 is gap has remained a long-standing open problem\, recently highlighted fo
 r its algorithmic significance by Apers et al. (FOCS '22). In this talk\,
  we show that any randomized two-round protocol for Graph Connectivity mus
 t communicate $\\Omega(n \\log n)$ bits\, matching the deterministic upper
  bound in this bounded-round setting. Our proof is based on a reduction fr
 om a restricted form of the Pointer Chasing problem\, originally studied b
 y Papadimitriou and Sipser (JCSS '84). Our reduction also allows us to ob
 tain $\\omega(n)$ lower bounds for any constant number of rounds\, by exte
 nding deterministic pointer-chasing bounds in prior work by Ponzio\, Radha
 krishnan\, and Venkatesh (JCSS '01) to the randomized setting. This is jo
 int work with Jaikumar Radhakrishnan (ICTS-TIFR\, Bengaluru) and Chaitanya
  Reddy (IIT Hyderabad).\nShort Bio: Rakesh Venkat is a faculty member at t
 he Indian Institute of Technology Hyderabad. He received his Ph.D. from th
 e Tata Institute of Fundamental Research (TIFR)\, Mumbai. His research int
 erests lie in approximation algorithms and computational complexity theory
 .\n
URL:https://www.tcs.tifr.res.in/web/events/1676
DTSTART;TZID=Asia/Kolkata:20260325T143000
DTEND;TZID=Asia/Kolkata:20260325T153000
LOCATION:A-201 Seminar Room
END:VEVENT
END:VCALENDAR