Tata Institute of Fundamental Research
Communication with Imperfectly Shared Randomness
Seminar
Speaker:
Madhu Sudan (Microsoft Research, New England)
Organiser:
Prahladh Harsha
Date:
Monday, 12 Jan 2015, 14:30 to 15:30
Venue:
AG-80
(Scan to add to calendar)
Abstract:
In 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 possible number of bits, to determine some function $f(x,y)$. For many natural functions $f$ this communication complexity is much smaller than the trivial $n$ bits suggesting that communication with a goal in mind may be much less expensive than otherwise. This message gets amplified even more if Alice and Bob share some random string $r$ chosen independently of $x$ and $y$: in this setting even more functions $f$ can be determined quickly (with high probability).
In 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 with $r$. I will describe some recent results showing that any communication protocol with $k$ bits of communication between Alice and Bob with perfect sharing of randomness, continues to have a moderately low-complexity, $2^k$ bit, protocol with shared correlation. Furthermore, I will show that this result is tight in that there exist problems where this exponential jump is necessary. The technical core of these results rely on the understanding of the influence of variables in the analysis of Boolean functions and recently developed probabilistic tools such as the ``invariance principle'' of Mossel, O'Donnell and Oleszkiewicz. The talk will assume no background in communication complexity and/or influence of variables.
Based on joint work with Clément Canonne (Columbia), Venkatesan Guruswami (CMU) and Raghu Meka (UCLA).
| Speaker: | Madhu Sudan (Microsoft Research, New England) |
| Organiser: | Prahladh Harsha |
| Date: | Monday, 12 Jan 2015, 14:30 to 15:30 |
| Venue: | AG-80 |
(Scan to add to calendar)
Abstract:
In 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 possible number of bits, to determine some function $f(x,y)$. For many natural functions $f$ this communication complexity is much smaller than the trivial $n$ bits suggesting that communication with a goal in mind may be much less expensive than otherwise. This message gets amplified even more if Alice and Bob share some random string $r$ chosen independently of $x$ and $y$: in this setting even more functions $f$ can be determined quickly (with high probability).
In 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 with $r$. I will describe some recent results showing that any communication protocol with $k$ bits of communication between Alice and Bob with perfect sharing of randomness, continues to have a moderately low-complexity, $2^k$ bit, protocol with shared correlation. Furthermore, I will show that this result is tight in that there exist problems where this exponential jump is necessary. The technical core of these results rely on the understanding of the influence of variables in the analysis of Boolean functions and recently developed probabilistic tools such as the ``invariance principle'' of Mossel, O'Donnell and Oleszkiewicz. The talk will assume no background in communication complexity and/or influence of variables.
Based on joint work with Clément Canonne (Columbia), Venkatesan Guruswami (CMU) and Raghu Meka (UCLA).
In 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 with $r$. I will describe some recent results showing that any communication protocol with $k$ bits of communication between Alice and Bob with perfect sharing of randomness, continues to have a moderately low-complexity, $2^k$ bit, protocol with shared correlation. Furthermore, I will show that this result is tight in that there exist problems where this exponential jump is necessary. The technical core of these results rely on the understanding of the influence of variables in the analysis of Boolean functions and recently developed probabilistic tools such as the ``invariance principle'' of Mossel, O'Donnell and Oleszkiewicz. The talk will assume no background in communication complexity and/or influence of variables.
Based on joint work with Clément Canonne (Columbia), Venkatesan Guruswami (CMU) and Raghu Meka (UCLA).