The communication-complexity tag has no usage guidance.

**3**

votes

**0**answers

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

**10**

votes

**1**answer

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