<p>The communication matrix of a function $f$ is a $2^{n}\times 2^{n}$ matrix $M_f$ where the indices of the rows (columns) correspond to the inputs of Alice (Bob), and each entry $M_f (a,b)$ is the function value $f(a,b)$.</p>

<p>The log-rank conjecture asserts that for the communication complexity $CC(f)$ it holds that $ CC(f) = (\log rank (M_{f}))^{O(1)}$.</p>

<p>Given $k\in\Bbb N$, is it known whether 
$$\mathsf{P}(CC(f) \leq (\log r)^{k})\geq1-\frac{1}{p(k)}$$ 
where the probability is over $0/1$ matrices $M_f$ of fixed rank $rank (M_{f})=r$, for a polynomial $p(x)\in\Bbb Z_{\geq0}[x]$ or 
$$\mathsf{P}(CC(f) \leq (\log r)^{k})\geq1-\frac{1}{n^k}$$ 
where the probability is over $2^n\times 2^n$ $0/1$-matrices $M_f$ of fixed rank $rank (M_{f})=r$ ?</p>

CC BY-SA 3.0
2015-03-10T06:28:32.413Z
By 'probability over $rank(M_f)$ matrices', do you mean you are randomly choosing different $f$ (and therefore $M_f$) of some constant rank, or if $f$ is fixed what is the random choice?
Joe Bebel
CC BY-SA 3.0
2015-03-10T06:30:54.073Z
different $M_f$.
Turbo
CC BY-SA 3.0
2015-03-10T11:40:11.163Z
I still don't understand what is being chosen at random. Can you be more precise? Do you randomly choose a Boolean matrix from the set of all Boolean matrices? Or randomly choose a Boolean matrix from the set of all Boolean matrices that have fixed rank r? Or something else?
Robin Kothari
CC BY-SA 3.0
2015-03-10T12:00:42.807Z
We choose $M_f$ uniformly from fixed rank $r$ matrices.
Turbo
<pr.probability><communication-complexity>
On a possible probabilistic log-rank conjecture
Turbo
# On a possible probabilistic log-rank conjecture

(Asked by: username_0 on 2015-03-10)

The communication matrix of a function $f$ is a $2^{n}\times 2^{n}$ matrix $M\_f$ where the indices of the rows (columns) correspond to the inputs of Alice (Bob), and each entry $M\_f (a,b)$ is the function value $f(a,b)$.

The log-rank conjecture asserts that for the communication complexity $CC(f)$ it holds that $ CC(f) = (\log rank (M\_{f}))^{O(1)}$.

Given $k\in\Bbb N$, is it known whether
$$\mathsf{P}(CC(f) \leq (\log r)^{k})\geq1-\frac{1}{p(k)}$$
where the probability is over $0/1$ matrices $M\_f$ of fixed rank $rank (M\_{f})=r$, for a polynomial $p(x)\in\Bbb Z\_{\geq0}[x]$ or
$$\mathsf{P}(CC(f) \leq (\log r)^{k})\geq1-\frac{1}{n^k}$$
where the probability is over $2^n\times 2^n$ $0/1$-matrices $M\_f$ of fixed rank $rank (M\_{f})=r$ ?

**Tags:** pr.probability, communication-complexity

> **Comments:**
> **username_1**: By 'probability over $rank(M_f)$ matrices', do you mean you are randomly choosing different $f$ (and therefore $M_f$) of some constant rank, or if $f$ is fixed what is the random choice?  
> **username_0**: different $M_f$.  
> **username_2**: I still don't understand what is being chosen at random. Can you be more precise? Do you randomly choose a Boolean matrix from the set of all Boolean matrices? Or randomly choose a Boolean matrix from the set of all Boolean matrices that have fixed rank r? Or something else?  
> **username_0**: We choose $M_f$ uniformly from fixed rank $r$ matrices.  

---

## 0 answers

