# Why does the log-rank conjecture use rank over the reals?

In communication complexity, the log-rank conjecture states that

$$cc(M) = (\log rk(M))^{O(1)}$$

Where $cc(M)$ is the communication complexity of $M(x,y)$ and $rk(M)$ is the rank of $M$ (as a matrix) over the reals.

However, when you are just using the rank-method to lower bound $cc(M)$ you can use $rk$ over any field that is convenient. Why does the log-rank conjecture restrict to rk over the reals? Is the conjecture resolved for $rk$ over fields of non-zero characteristic? If not, is it of interest or is there something special about $rk$ over $\mathbb{R}$?

• BTW I believe you should restrict $M$ to be binary, otherwise you can make up trivial counterexamples. – Sasho Nikolov Apr 23 '13 at 3:48
• @SashoNikolov What do you mean by trivial counterexamples if $M$ is not $0/1$ (I believe you mean over reals)? – T.... Jan 20 '15 at 10:52
• For example the problem "guess my number", i.e. Alice has a number in $\{1, \ldots, N\}$ and Bob has to output it. It's easy to see the communication complexity is $\log N$ but the rank of the matrix is $1$. – Sasho Nikolov Jan 20 '15 at 16:30
• @SashoNikolov Can you define guess my number precisely? I am unable to visualize the characteristic matrix. Alice has $x$ and Bob has $y$, then what is function $f(x,y)$ from which $M$ of rank $1$ is defined? – T.... Jan 20 '15 at 21:08
• The function is $f(x, y) = x$ where $x$ and $y$ are $n$-bit vectors. If the definition of communication complexity requires that the value of $f$ be determined entirely by the protocol transcript (this is the definition in Kushilevitz-Nisan), then clearly the complexity is $n$. – Sasho Nikolov Jan 20 '15 at 21:52

The conjecture fails over $\mathbb{F}_2$. Look at $M(x, y) = \langle x, y \rangle \bmod 2$, and $x, y \in \{0, 1\}^n$. The communication complexity is $\Omega(n)$, but the rank of $M$ over $\mathbb{F}_2$ is $n$, by the linearity of inner product.