The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
0answers
212 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
1answer
436 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 ...