BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/600
DTSTAMP:20230914T125931Z
SUMMARY:Clique vs Independent Set Game: A Tight Bound
DESCRIPTION:Speaker: Sagnik  Mukhopadhyay\n\nAbstract: \nAbstract: The cliq
 ue vs independent set game (CIS(G)) on a graph $G$ is a game between two p
 arties - Alice and Bob. Alice get s a set of vertices\, $C$\,  which form
 s a clique in $G$ and Bob gets a set of vertices\, $I$\, which forms an in
 dependent set in $G$. Clearly\, $C$ and $I$ can intersect in only 1 vertex
 . The question the players try to answer is whether $C \\cap I = \\emptyse
 t$ or not.\n\nBy a result of Yannakakis\, we know that this problem can be
  solved deterministically by communicating $O(\\log^2 n)$ bits where $n$ i
 s the size of vertex set in $V$. It has been an open problem for a long ti
 me whether this upper bound can be improved.\n\nA recent result of Goos\, 
 Pitassi and Watson shows that this upper bound is tight\, i.e.\, there is 
 a graph for which the CIS game requires $\\tilde{\\Omega}(\\log^2 n)$ comm
 unication. In the talk\, we will see proof-sketches of these results.\n
URL:https://www.tcs.tifr.res.in/web/events/600
DTSTART;TZID=Asia/Kolkata:20150515T140000
DTEND;TZID=Asia/Kolkata:20150515T153000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR