10
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ BTW I believe you should restrict $M$ to be binary, otherwise you can make up trivial counterexamples. $\endgroup$ – Sasho Nikolov Apr 23 '13 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$ – T.... Jan 20 '15 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$ – Sasho Nikolov Jan 20 '15 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$ – T.... Jan 20 '15 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$ – Sasho Nikolov Jan 20 '15 at 21:52
14
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

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.