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