<p>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. </p>

CC BY-SA 3.0
2013-04-23T02:48:58.543Z
2013-04-23T02:48:58.543Z
Sasho Nikolov
<p>In communication complexity, the log-rank conjecture states that</p>

<p>$$cc(M) = (\log rk(M))^{O(1)}$$</p>

<p>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.</p>

<p>However, when you are just using the rank-method to lower bound $cc(M)$ you can use $rk$ over any field that is convenient. <strong>Why does the log-rank conjecture restrict to rk over the reals?</strong> 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}$?</p>

CC BY-SA 3.0
2013-04-23T03:48:27.573Z
BTW I believe you should restrict $M$ to be binary, otherwise you can make up trivial counterexamples.
Sasho Nikolov
CC BY-SA 3.0
2015-01-20T10:52:38.987Z
@SashoNikolov What do you mean by trivial counterexamples if $M$ is not $0/1$ (I believe you mean over reals)?
Turbo
CC BY-SA 3.0
2015-01-20T16:30:31.820Z
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
CC BY-SA 3.0
2015-01-20T21:08:24.443Z
@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?
Turbo
CC BY-SA 3.0
2015-01-20T21:52:43.660Z
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
CC BY-SA 3.0
2015-01-20T22:33:56.517Z
Rank is indeed $1$ since each column can be obtained by another by real multiplication. Do you know answer to http://cstheory.stackexchange.com/questions/29215/on-notion-of-positive-rank?
Turbo
<cc.complexity-theory><big-picture><linear-algebra><open-problem><communication-complexity>
Why does the log-rank conjecture use rank over the reals?
Artem Kaznatcheev
# Why does the log-rank conjecture use rank over the reals?

(Asked by: username_0 on 2013-04-23)

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

**Tags:** cc.complexity-theory, big-picture, linear-algebra, open-problem, communication-complexity

> **Comments:**
> **username_1**: BTW I believe you should restrict $M$ to be binary, otherwise you can make up trivial counterexamples.  
> **username_2**: @SashoNikolov What do you mean by trivial counterexamples if $M$ is not $0/1$ (I believe you mean over reals)?  
> **username_1**: 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$.  
> **username_2**: @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?  
> **username_1**: 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$.  
> **username_2**: Rank is indeed $1$ since each column can be obtained by another by real multiplication. Do you know answer to http://cstheory.stackexchange.com/questions/29215/on-notion-of-positive-rank?  

---

## 1 answers

### Answer by username_1 on 2013-04-23. Score: 14 | Accepted answer

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.


---

