Communication is bounded by root of rank

Introduction

Let $f:X\times Y\to\{-1,1\}$ be a boolean function with rank $r$. Then there exists a deterministic protocol computing $f$ which uses $O(\sqrt{r}\cdot\log r)$ bits of communication.

The log-rank conjecture can be equivalently formulated as the relation between the rank of the adjacency matrix of a graph and its chromatic number. In this formulation, Theorem 1.1 shows that any graph with adjacency matrix of rank $r$ has chromatic number at most $2^{O(\sqrt{r}\cdot\log r)}$.

The proof is based on analyzing the discrepancy of boolean functions. The discrepancy of a boolean function $f$ is given by

where $\mu$ ranges over all distributions over $X\times Y$ and $R$ ranges over all rectangles, e.g. $R=A\times B$ for $A\subset X,B\subset Y$. Discrepancy is a well-studied property in the context of communication complexity lower bounds, see e.g. for an excellent survey. It is known that low-rank matrices have noticeable discrepancy : if $f$ has rank $r$ then

Finally, we apply a theorem of Nisan and Wigderson , who showed that in order to establish that low rank matrices have efficient deterministic protocols, it suffices to show that they have large monochromatic rectangles (which is what we just showed).

As the proof in is shown only for the special case related to the log-rank conjecture, we include a proof sketch of Theorem 1.4 for general function $c(r)$, in Section 4.1. Theorem 1.1 now follows by setting $c(r)=O(\sqrt{r}\cdot\log(r))$.

2 Related works

A recent work of Tsang et al established similar bounds to Theorem 1.1 for the special case of functions of the form $f(x,y)=F(x\oplus y)$. Although the results are similar, the techniques seem to be different. In particular, the main tool used in is Fourier analysis, while our results are based on discrepancy. It would be interesting to understand if there are deeper connections between these techniques. Another recent work of Gavinsky and the author showed that in order to prove the log-rank conjecture, it suffices to show that any low rank matrix has an efficient randomized protocol, a low information cost protocol, or an efficient zero-communication protocol.

We give preliminary definitions in Section 2. We prove Lemma 1.2 in Section 3. We prove Theorem 1.1 in Section 4. We give a proof sketch of Theorem 1.4 in Section 4.1. We discuss a conjecture related to matrix rigidity in Section 5, and further open problems in Section 6.

Preliminaries

For standard definitions in communication complexity we refer the reader to . We give here only the basic definitions we would require.

The rank of $f$ is the rank (over the reals) of its associated $X\times Y$ matrix. The discrepancy of $f$ with respect to a distribution $\mu$ on $X\times Y$ is the maximal bias achieved by a rectangle,

The discrepancy of $f$ is the minimal discrepancy possible over all possible distributions $\mu$,

Note that discrepancy is an hereditary property. That is, if $R$ is a rectangle then the discrepancy of $f$ restricted to $R$ is at least the original discrepancy of $f$. Similarly, low rank is an hereditary property, as ranks of sub-matrices cannot exceed the rank of the original matrix. We will rely on the following theorem which lower bounds the discrepancy of functions with low rank.

An amplification lemma

Our main technical lemma is the following lemma, which shows that any boolean function with high discrepancy contains a large rectangle which is nearly monochromatic.

We note that Lemma 1.2 from the introduction is a special case of Lemma 3.1 where $\mu$ is chosen to be the uniform distribution. Our original proof of Lemma 3.1 used an iterative amplification step. After giving a talk on this result in the Banff complexity workshop, Salil Vadhan suggested to us a simplified proof, which avoids the iterative step by applying Yao’s mini-max principle. We present his proof below.

Let $R_{1}=A\times B$ and define $A^{\prime}=X\setminus A,B^{\prime}=Y\setminus B$. Consider the four rectangles

Let $p$ be the minimal probability that $(x_{1},y_{1})\in R$ over all $(x_{1},y_{1})\in f^{-1}(1)$, where $R$ is sampled according to $\rho$; and let $q$ be the maximal probability that $(x_{2},y_{2})\in R$ over all $(x_{2},y_{2})\in f^{-1}(-1)$. We established that

Fix $t\geq 1$ and let $R_{1},\ldots,R_{t}\sim\rho$ be chosen independently, and let $R^{*}=R_{1}\cap\ldots\cap R_{t}$ be their intersection. We will show that for an appropriate choice of $t$, the rectangle $R^{*}$ satisfies the requirements of the lemma with positive probability (and hence such a rectangle exists). We will use the fact that for any $x\in X,y\in Y$,

Let $R^{*}$ be a rectangle which achieves this average, that is

Deterministic protocols for low rank functions

We recall Theorem 1.1 for the convenience of the reader.

Theorem 1.1 (restated). Let $f:X\times Y\to\{-1,1\}$ be a boolean function with rank $r$. Then there exists a deterministic protocol computing $f$ which uses $O(\sqrt{r}\cdot\log r)$ bits of communication.

Next, we apply a claim from which shows that nearly monochromatic rectangles in low rank matrices contain large monochromatic matrices.

By Markov inequality, $|A^{\prime}|\geq|A|/2$. Let $x_{1},\ldots,x_{r}\in A^{\prime}$ be indices so that their rows span $A^{\prime}\times B$. Let

Since each of the rows $x_{1},\ldots,x_{r}$ contain at most $1/2r$ fraction of elements which are $-1$ we have $|B^{\prime}|\geq|B|/2$. Now, this implies that all rows in $A^{\prime}\times B^{\prime}$ are either the all one or all minus one. Choosing the largest half gives the required rectangle. ∎

Hence, we showed that any function $f:X\times Y\to\{-1,1\}$ of rank $r$ contains a monochromatic rectangle of size $2^{-O(\sqrt{r}\cdot\log(r))}\cdot|X\times Y|$. Applying Theorem 1.4 with $c(r)=O(\sqrt{r}\cdot\log(r))$, we conclude that any such function can be computed by a deterministic protocol which used $O(\sqrt{r}\cdot\log(r))$ bits of communication.

We recall Theorem 1.4 of Nisan and Wigderson for the convenience of the reader.

Let $f$ be a function of rank $r$, and consider the partition of its corresponding matrix as

Consider the protocol which stops once the rank drops to $r/2$. The protocol tree in this case has at most $O(2^{c(r)}\cdot\log(m))$ leaves, and hence can be simulated by a protocol sending only $O(c(r)+\log\log(m))$ bits. Note that since we can assume $f$ has no repeated rows or columns, $m\leq 2^{2r}$ and hence $\log\log(m)\leq\log(r)+1$. Next, consider the phase where the protocol continues until the rank drops to $r/4$. Again, this protocol can be simulated by $O(c(r/2)+\log(r))$ bits of communication. Summing over $r/2^{i}$ for $i=0,\ldots,\log(r)$ gives the bound. ∎

A conjecture related to matrix rigidity

The proof of Theorem 1.1 relies on the matrix $f$ being boolean. However, we conjecture that it can be generalized to show that any low rank sparse matrix contains a large zero rectangle.

such that $|A|,|B|\geq n\cdot\exp(-O(\sqrt{\varepsilon r}))$.

The bound in Conjecture 5.1, if true, is the best possible, as the following example shows. Let $M=NN^{t}$ where $N$ is an $n\times r$ matrix whose rows are all the $\{0,1\}^{r}$ vectors of hamming weight $\sqrt{r}/10$, and $n={r\choose\sqrt{r}/10}=r^{\Omega(\sqrt{r})}$. The matrix $M$ is $\varepsilon=1/100$ sparse, as the probability that two uniformly chosen vectors intersect is at most $1/100$. However, one can verify that the largest subsets $A,B\subset[n]$ such that $M_{a,b}=0$ for all $a\in A,b\in B$ correspond to choosing $A$ to be all vectors whose support lies in the first half of the coordinates, and $B$ to be all vectors whose support lies in the last half of the coordinate. Furthermore, $|A|,|B|\leq n\cdot\exp(-\Omega(\sqrt{r}))$. The bound for general $\varepsilon>0$ can be similarly obtained, by considering all vectors in $\{0,1\}^{r}$ of hamming weight $\sqrt{\varepsilon r}$.

A matrix $M$ is called $(r,s)$-rigid, if its rank cannot be made smaller than $r$ by changing at most $s$ entries in $M$. The problem of explicitly constructing rigid matrices was introduced by Valiant in the context of arithmetic circuits lower bounds, and was also studied by Razborov in the context of separation of the analogs of PH and PSPACE in communication complexity. Despite much research, the best results to date are achieved by the so-called ”untouched minor” argument, which gives explicit matrices which are $(r,s)$-rigid with $s=\Omega\left(\frac{n^{2}}{r}\log\left(\frac{n}{r}\right)\right)$. See e.g. the excellent survey of Lokam for details. We will prove the following corollary of Conjecture 5.1, which improves previous bounds by a logarithmic factor.

Assuming Conjecture 5.1, there exists an explicit $n\times n$ real matrix which is $(r,s)$-rigid for $s=\Omega\left(\frac{n^{2}}{r}\log^{2}\left(\frac{n}{r}\right)\right)$.

Let $M$ be an $n\times n$ matrix of rank $r$, such that all $r\times r$ minors of $M$ have full rank. For example, such a matrix may be constructed as $M=NN^{t}$ where $N$ is an $n\times r$ matrix such that any $r$ rows of $N$ are linearly independent. Assume that $M$ is not $(r,s)$-rigid. Then, we can decompose

Further research

I thank Dmitry Gavinsky, Pooya Hatami, Russell Impagliazzo and Adi Shraibman for helpful discussions, and Salil Vadhan for allowing to present his simplified proof of Lemma 3.1.

References