Questions tagged [communication-complexity]
The communication-complexity tag has no usage guidance.
4
questions
3
votes
0answers
67 views
Quantum versus classical communication complexity
Problem. Is it true that any 2-party communication problem $f(x,y)$ of poly-logarithmic complexity in the quantum simultaneous message passing model ($Q''$) has complexity $n^{o(1)}$ (i.e., strongly ...
2
votes
1answer
195 views
Entropy x Complexity - Shannon x Kolmogorov [closed]
This is a very common question but I think I’m posting it in a different way.
Suppose that we have 256 different possible messages with uniform distribution to be represented in a binary code. Then ...
3
votes
0answers
299 views
what is the largest gap between rank and approximate rank
$\epsilon$-approximation rank of a matrix $M$ is the minimum rank of a real matrix $A$ which differs from $M$ at most $\epsilon$ in each entry. Associating any function $f:X\times Y\rightarrow${1,-1} ...
13
votes
1answer
567 views
Space Bounded Communication Complexity of Identity
$\bf Definition.$ We define the space bounded communication in the following way. A and B are
supernatural beings capable of computing anything but
they only have a limited amount of memory and that ...
