Space Bounded Communication Complexity of Identity

Question

$\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)$.

Answer 1

Here's an argument that I believe shows that $\log n - \omega(1)$ is impossible. (This argument came out of a discussion I had with Steve Fenner.)

Let Alice's input be $x\in\{0,1\}^n$ and let Bob's input be $y\in\{0,1\}^n$. Assume the shared memory stores states in $\{0,1\}^m$, and its initial state is $0^m$. We are interested in lower-bounding $m$ for any protocol that computes EQ$(x,y)$.

A given protocol is defined by two collections of functions $\{f_x\}$ and $\{g_y\}$, representing the functions applied to the shared memory by Alice on each input $x$ and Bob on each input $y$, respectively, along with some answering criterion. To be more specific, let us assume that if the shared memory ever contains the string $1^{m-1}b$ then the output of the protocol is $b$ (for each $b\in\{0,1\}$). For convenience, let us also assume that $f_x(1^{m-1}b) = 1^{m-1}b\:$ and $g_y(1^{m-1}b) = 1^{m-1}b\:$ for every $x,y\in\{0,1\}^n$ and $b\in\{0,1\}$. In other words, Alice and Bob don't change the shared memory once they know the answer.

Now, for each $x,y\in\{0,1\}^n$, consider what happens when Alice and Bob run the protocol on the input $(x,y)$. Define $A_{x,y}\subseteq\{0,1\}^m$ to be the set of all states of the shared memory that Alice receives at any point in the protocol, and likewise define $B_{x,y}\subseteq\{0,1\}^m$ to be the states of the shared memory that Bob receives. Also define $$ S_{x,y} = \{0w\,:\,w\in A_{x,y}\} \cup \{1w\,:\,w\in B_{x,y}\}.$$ We will assume Alice goes first, so $0^m \in A_{x,y}$ for all $x,y$. Let us also make the following observations:

1. By the definition of $A_{x,y}$ and $B_{x,y}$, it holds that $f_x(A_{x,y}) \subseteq B_{x,y}$ and $g_y(B_{x,y}) \subseteq A_{x,y}$ for all $x,y$.

2. For every $x,y$ with $x\not=y$ it holds that $1^{m-1}0\in A_{x,y} \cup B_{x,y}$, because Alice and Bob output 0 when their strings disagree.

3. For every $x$ it holds that $1^{m-1}0\not\in A_{x,x} \cup B_{x,x}$, because Alice and Bob do not output 0 when their strings agree.

Now let us prove that $S_{x,x}\not=S_{y,y}$ whenever $x\not=y$. To do this, let us assume toward contradiction that $x\not=y$ but $S_{x,x} = S_{y,y}$ (i.e., $A_{x,x} = A_{y,y}$ and $B_{x,x} = B_{y,y}$), and consider the behavior of the protocol on the input $(x,y)$.

Let $w_t$ be the contents of the shared memory after $t$ turns have passed in the protocol, so we have $w_0 = 0^m$, $w_1 = f_x(w_0)$, $w_2 = g_y(w_1)$, and so on. It holds that $$ \begin{array}{c} w_0 = 0^m \in A_{x,x}\\ w_1 = f_x(w_0) \in f_x(A_{x,x}) \subseteq B_{x,x} = B_{y,y},\\ w_2 = g_y(w_1) \in g_y(B_{y,y}) \subseteq A_{y,y} = A_{x,x}, \end{array} $$ and in general $$ \begin{array}{c} w_{2t + 1} = f_x(w_{2t}) \in f_x(A_{x,x}) \subseteq B_{x,x} = B_{y,y}\\ w_{2t+2} = g_y(w_{2t+1}) \in g_y(B_{y,y}) \subseteq A_{y,y} = A_{x,x} \end{array} $$ for each $t\in\mathbb{N}$. It follows that $A_{x,y} \subseteq A_{x,x}$ and $B_{x,y} \subseteq B_{y,y}$.

But now we have our contradiction, assuming the protocol is correct: given that $A_{x,y}\subseteq A_{x,x}$ and $B_{x,y} \subseteq B_{y,y}$, it follows that $1^{m-1}0 \in A_{x,x}\cup B_{y,y}$, so Alice and Bob output the incorrect answer 0 on either $(x,x)$ or $(y,y)$.

Each $S_{x,x}$ is a subset of $\{0,1\}^{m+1}$, so there are at most $2^{2^{m+1}}$ choices for $S_{x,x}$. Given that the sets $S_{x,x}$ must be distinct for distinct choices of $x$, it follows that $2^{2^{m+1}} \geq 2^n$, so $m \geq \log n - 1$.