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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.