Space Bounded Communication Complexity of Identity

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 $xin{0,1}^n$ and let Bob's input be $yin{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 $bin{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,yin{0,1}^n$ and $bin{0,1}$. In other words, Alice and Bob don't change the shared memory once they know the answer.

Now, for each $x,yin{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,:,win A_{x,y}} cup {1w,:,win 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 $xnot=y$ it holds that $1^{m-1}0in 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}0notin 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 $xnot=y$. To do this, let us assume toward contradiction that $xnot=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 $tinmathbb{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$.