Questions tagged [communication-complexity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...