BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/564
DTSTAMP:20230914T125929Z
SUMMARY:Communication with Imperfectly Shared Randomness
DESCRIPTION:Speaker: Madhu Sudan (Microsoft Research\, New England)\n\nAbst
 ract: \nIn the 1980's Yao introduced the model of communication complexity
  where Alice\, who knows $x$ in ${0\,1}^n$\, and Bob\, who knows $y$ in ${
 0\,1}^n$\, wish to communicate with each other\, exchanging fewest possibl
 e number of bits\, to determine some function $f(x\,y)$. For many natural 
 functions $f$ this communication complexity is much smaller than the trivi
 al $n$ bits suggesting that communication with a goal in mind may be much 
 less expensive than otherwise. This message gets amplified even more if Al
 ice and Bob share some random string $r$ chosen independently of $x$ and $
 y$: in this setting even more functions $f$ can be determined quickly (wit
 h high probability).\n\nIn this talk I will introduce a relaxation of this
  model where Alice and Bob do not share the random string perfectly\, but 
 rather Alice knows $r$ and Bob knows some string $s$ that is correlated wi
 th $r$. I will describe some recent results showing that any communication
  protocol with $k$ bits of communication between Alice and Bob with perfec
 t sharing of randomness\, continues to have a moderately low-complexity\, 
 $2^k$ bit\, protocol with shared correlation. Furthermore\, I will show th
 at this result is tight in that there exist problems where this exponentia
 l jump is necessary. The technical core of these results rely on the under
 standing of the influence of variables in the analysis of Boolean function
 s and recently developed probabilistic tools such as the ``invariance prin
 ciple'' of Mossel\, O'Donnell and Oleszkiewicz. The talk will assume no ba
 ckground in communication complexity and/or influence of variables.\n\nBas
 ed on joint work with Clément Canonne (Columbia)\, Venkatesan Guruswami (
 CMU) and Raghu Meka (UCLA).\n
URL:https://www.tcs.tifr.res.in/web/events/564
DTSTART;TZID=Asia/Kolkata:20150112T143000
DTEND;TZID=Asia/Kolkata:20150112T153000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR
