Communication complexity: fooling set bound for inner product function

Question

I am trying to prove that the fooling set method does not give a good lower bound for the communication complexity of the inner product function. Specifically, I am trying to show that the best bound we get using the fooling set method is $$D(IP) \geq \Omega(\log n) $$

$D(IP)$ is the deterministic communication complexity of the inner product function. This implies that any fooling set for the inner product cannot have more than $n^2$ elements. How do I show this? I can verify the statement for specific instances, but I have no intuition for the proof.

Answer 1

Let $(x_i,y_i)$ be a fooling set for inner product, of size $m$. Construct an $m \times n$ matrix $X$ whose rows are $x_i$ and an $n \times m$ matrix $Y$ whose columns are $y_i$, and consider the matrix $M = XY$ (arithmetic is over the field $\mathbb{F}_2$). The decomposition $M=XY$ shows that $M$ has rank at most $n$.

Suppose first that $\mathrm{IP}(x_i,y_i) = 1$ for all $i$, and so for each $i \neq j$, either $\mathrm{IP}(x_i,y_j) = 0$ or $\mathrm{IP}(x_j,y_i) = 0$. Consider the Hadamard (entrywise) product of $M$ and $M^T$. It is known that rank is submultiplicative with respect to entrywise product, and so the rank of $M \circ M^T$ is at most $n^2$. On the other hand, $M \circ M^T$ is the identity matrix, and so has rank $m$. We conclude that $m \leq n^2$.

When $\mathrm{IP}(x_i,y_i) = 0$ for all $i$, we consider the matrix $M' = M+J$, where $J$ is the all ones matrix. Since $J$ has rank 1, the rank of $M'$ is at most $n+1$, and so the argument in the preceding paragraph shows that $m \leq (n+1)^2$.