BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/772
DTSTAMP:20230914T125937Z
SUMMARY:On the Communication and Streaming Complexity of Maximum Bipartite 
 Matching
DESCRIPTION:Speaker: Sumedh Vinod Tirodkar\n\nAbstract: \nConsider the foll
 owing communication problem. Alice holds a graph $G_A = (P\, Q\, E_A)$ and
  Bob holds a graph $G_B = (P\, Q\, E_B)$\, where $|P| = |Q| = n$. Alice is
  allowed to send Bob a message $m$ that depends only on the graph $G_A$. B
 ob must then output a matching $M\\subseteq E_A \\cup E_B$. What is the mi
 nimum message size of the message $m$ that Alice sends to Bob that allows 
 Bob to recover a matching of size at least $(1 - \\epsilon)$ times the max
 imum matching in $G_A \\cup G_B$? The minimum message length is the one-ro
 und communication complexity of approximating bipartite matching. It is ea
 sy to see that the one-round communication complexity also gives a lower b
 ound on the space needed by a one-pass streaming algorithm to compute a $(
 1 - \\epsilon)$-approximate bipartite matching. Using connection to $\\eps
 ilon$-RS graphs\, the authors show that for any $\\delta>0$\, a $(2/3+\\de
 lta)$-approximation requires a communication complexity of $n^{1+\\Omega(1
 /\\log\\log n)}$. And thus\, no one-pass semi-streaming algorithm can have
  a $(2/3+\\delta)$-approximation ratio (authors: Ashish Goel\, Michael Kap
 ralov\, Sanjeev Khanna).\n
URL:https://www.tcs.tifr.res.in/web/events/772
DTSTART;TZID=Asia/Kolkata:20170421T171500
DTEND;TZID=Asia/Kolkata:20170421T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR