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}$?

  • 2
    $\begingroup$ BTW I believe you should restrict $M$ to be binary, otherwise you can make up trivial counterexamples. $\endgroup$ Commented Apr 23, 2013 at 3:48
  • $\begingroup$ @SashoNikolov What do you mean by trivial counterexamples if $M$ is not $0/1$ (I believe you mean over reals)? $\endgroup$
    – Turbo
    Commented Jan 20, 2015 at 10:52
  • $\begingroup$ 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$. $\endgroup$ Commented Jan 20, 2015 at 16:30
  • $\begingroup$ @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? $\endgroup$
    – Turbo
    Commented Jan 20, 2015 at 21:08
  • 1
    $\begingroup$ 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$. $\endgroup$ Commented Jan 20, 2015 at 21:52

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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