$\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 is shared. The minimum size of this common memory that they can use to evaluate a given function $f$ for which both of them possesses one half of the input, resp. $x$ and $y$, shall be denoted by $S(f)$. At the beginning it is filled with zeros. Then in each step one of the players can put there an arbitrary message depending only on the previous message and his input. They are finished when both of them knows the value of $f(x,y)$. We can also imagine this as two people communicating who have no memory at all (however, they can remember their own input) and are allowed to send each other a rewritable disk. The question is how big the disk has to be if both of them wants to know the value of $f(x,y)$.

Define the identity function as $I(x,y): \{0,1\}^n\times \{0,1\}^n\rightarrow \{0,1\}$ with $I=1$ if and only if $x=y$.

$\bf Question.$ How much is $S(I)$?

$\bf Remarks.$ I know it is between $\log n$ and $\log n - \log \log n$, but which? Is it possible to solve it in $\log n-\omega(1)$ space? Anyone heard of any related things?

$\bf Example/Easy Claim.$ $S(I) \le \log(n) + O(1)$. $\bf Proof.$ We present a construction. A sends her bits one after the other along with their ordinal number and a leading 1, meaning that it is up to B to speak. B replies to each message with his bit with the same ordinal number and a leading 0. This requires $2 + \log n$ space. If in a step his bit differs from her, they know that the answer is 0, the algorithm is over. If they finish sending all their bits, the answer is 1. Therefore, $S(I) \leq \log n + O(1)$.

5more comments