All Questions
Tagged with communication-complexity information-theory
6 questions
1
vote
0
answers
47
views
Communication Complexity of "2-Bit"
[For context, I'm trying to work through the derivation of Lemma 2.1 (2-Bit) here, https://users.cs.utah.edu/~jeffp/papers/multiCC-soda12.pdf. ]
The '2-Bit' setup is that Alice draws a bit-string of ...
- 46
1
vote
1
answer
48
views
Can a static pre-shared database reduce communication size?
Is the problem of communication with a pre-shared database studied? If yes, what field studies it, or which researchers work on it?
Let there be two parties that want to share multiple yet-to-be-...
2
votes
1
answer
227
views
Deriving a lower bound on the conditional entropy, conditioned on an event
I came across Lemma 19 in Certifying Equality With Limited Interaction, which states the following for jointly distributed random variables $Z$, $W$, where $Z$ takes values in $\{0,1\}^n$, and some ...
- 23
1
vote
0
answers
96
views
Decomposition of Mutual Information [closed]
I came across a book where the author uses the following property of mutual information:
Let $X$,$Y$,$Z$ be arbitrary discrete random variables and let $W$ be an indicator random variable.
$$
(1)\ \ ...
- 33
3
votes
1
answer
92
views
Upper bound for set disjointness under product distributions
For the set disjointness problem in the 2-party model of communication complexity, Alice is given an input $X$ and Bob is given input $Y$, $X$ and $Y$ are $n$-length bitstrings (sampled from some ...
3
votes
1
answer
117
views
Understanding the flaw in a proof attempt of the Communication Complexity of Equality
I'm new to communication theory and I've been wondering where the following simple argument fails:
Equality Problem
We have two players, player 1 Alice who gets an $n$-bit vector $X$ and player 2 Bob ...
- 31