# Questions tagged [communication-complexity]

The communication-complexity tag has no usage guidance.

4
questions

**3**

votes

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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 ...