\( \def\<#1>{\left<#1\right>} \newcommand{\OR}[1]{\mathrm{OR}(#1)} \newcommand{\XOR}[1]{\mathrm{XOR}(#1)} \newcommand{\SUM}[1]{\mathrm{SUM}(#1)} \newcommand{\Geq}{\succcurlyeq} \newcommand{\Leq}{\preccurlyeq} \newcommand{\co}[1]{\overline{#1}} \newcommand{\rk}{{\rm rk}\,} \newcommand{\oA}{\overline{A}} \newcommand{\oB}{\overline{B}} \newcommand{\oM}{\overline{M}} \newcommand{\pr}[1]{\mathrm{rk}_+(#1)} \newcommand{\br}[1]{\mathrm{rk}_{\lor}(#1)} \newcommand{\FF}{\mathbb{F}_2} \newcommand{\NN}{\mathbb{N}} \newcommand{\dec}[1]{\chi(#1)} \newcommand{\Dec}[2]{\chi_{#2}(#1)} \newcommand{\nc}[1]{\mathfrak{nc}(#1)} \newcommand{\cc}[1]{\mathfrak{c}(#1)} \newcommand{\cov}[2]{\mathrm{Cov}_{#2}(#1)} \newcommand{\bp}[2]{\mathrm{bp}_{#2}(#1)} \newcommand{\rk}[1]{\mathrm{rk}(#1)} \)

Tilling matrices and their complements

Recall that the tiling number of a boolean matrix $A$ is $\dec{A}=\Dec{A}{0}+\Dec{A}{1}$, where $\Dec{A}{\sigma}$ for $\sigma\in\{0,1\}$ is the minimum number of pairwise disjoint all-$\sigma$ submatrices of $A$ covering all its $\sigma$-entries. It is clear that if $A$ is an $n\times n$ matrix, then $\Dec{A}{0}\leq n$ and $\Dec{A}{1}\leq n$: single rows give us disjoint monochromatic submatrices. The logarithm $\log\dec{A}$ of the tiling number of matrices $A$ is a trivial lower bound on their the deterministic communication complexity $\cc{A}$. We also know that \begin{equation}\label{eq:1} \cc{A}\Leq \log^2\dec{A}\qquad\mbox{ and even }\qquad \cc{A}\Leq \log^2\Dec{A}{1}\,, \end{equation} where the former upper bound is due to Aho, Ullman and Yannakakis (1983), and the latter is due to Yannakakis (1991).

An old problem was: how well does the tiling number captures the deterministic communication complexity? Kushilevitz, Linial, and Ostrovsky (1999) have shown (via a rather nontrivial argument) that $\cc{A}\geq 2\cdot \log\dec{A}$ holds for some matrices $A$. Göös, Pitassi, and Watson (2018) have substantially improved this lower bound to \[ \cc{A}\Geq \log^{1.5-o(1)}\dec{A}\qquad\mbox{ and }\qquad \cc{A}\Geq \log^{2-o(1)}\Dec{A}{1}\,. \] Note that the latter lower bound is essentially tight since $\cc{A}\Leq \log^2\Dec{A}{1}$.

But what about the relation between the combinatorial measures $\Dec{A}{0}$ and $\Dec{A}{1}$ themselves?

Question: Can $\Dec{A}{0}$ be much larger than $\Dec{A}{1}$?
By the second inequality in \eqref{eq:1}, we have \begin{equation}\label{eq:2} \log\Dec{A}{0}\leq \log \dec{A}\leq \cc{A}\Leq \log^2\Dec{A}{1}\,. \end{equation}

Note that $\Dec{A}{0}=\Dec{\co{A}}{1}$, where $\co{A}$ is the complement of the matrix $A$. Hence, the question actually is: can the ones of a matrix be decomposed into much smaller number of rectangles (all-$1$ matrices) than those of the complement matrix?

Below we show that recent results concerning biclique coverings and the clique vs. independent set problem answer the above question affirmatively.

Remark: Combinatorial measures of matrices corresponding to their nondeterministic communication complexity are the cover numbers $\cov{A}{0}$ and $\cov{A}{1}$, where $\cov{A}{\sigma}$ is the minimum number of not necessarily disjoint all-$\sigma$ submatrices of $A$ covering all its $\sigma$-entries. Then $\log\cov{A}{1}$ is exactly the nondeterministic communication complexity of the matrix $A$. These two measures can exponentially differ on already very simple matrices. For example, if $A=\overline{I_n}$ is the complement of the $n\times n$ identity matrix $I_n$, then \[ \cov{A}{0}\geq 2^{\cov{A}{1}/2}\,. \] The lower bound $\cov{I_n}{1}\geq n$ is trivial: no two $1$-entries of $I_n$ can belong to the same all-$1$ submatrix. The upper bound $\cov{\overline{I_n}}{0}\leq 2\log n$ is also easy to see by labeling the rows and columns by binary vectors of length $\log n$, and considering rectangles differing in one bit of the labels.

Biclique coverings of graphs

Fix some set of vertices, say $V=\{1,\ldots,n\}$. A biclique $B(X,Y)$ is specified by an ordered pair $(X,Y)$ of disjoint subsets of vertices (color classes), and consists of all edges $\{u,v\}$ with $u\in X$ and $v\in Y$, or $u\in Y$ and $v\in X$. A biclique $k$-covering of a graph $G=(V,E)$ is a collection $B(X_1,Y_1),\ldots,B(X_t,Y_t)$ of bicliques lying in $E$ such that every edge $e\in E$ belongs to at least one and to at most $k$ of these bicliques. Let $\bp{G}{k}$ denote the minimum number $t$ of bicliques in such a covering of $G$.

A classical result of Graham and Pollak (1971) is that $\bp{K_n}{1}=n-1$ holds for the complete $n$-vertex graph $K_n$. Alon (1997) substantially extended this result by showing that $\bp{K_n}{k}=\Theta(k n^{1/k})$ holds for every $k\geq 1$.

A biclique $1.5$-covering of a graph $G$ is a biclique $2$-covering $B(X_1,Y_1),\ldots,B(X_t,Y_t)$ of $G$ such that $(X_i\times Y_i)\cap (X_j\cap Y_j)=\emptyset$ for all $i\neq j$. That is, we now consider disjoint rectangles $X_i\times Y_i$ ("directed" versions of bicliques $B(X_i,Y_i)$), and the requirement is that for every edge $\{u,v\}$ of $G$, either $(u,v)$ or $(v,u)$ belongs to at least one of the rectangles $X_i\times Y_i$.

It is clear that $\bp{G}{2}\leq \bp{G}{1.5}\leq \bp{G}{1}$ holds for every graph $G$. For the complete graph, Alon's result yields $\bp{G}{1.5}\geq \bp{G}{2}\Geq n^{1/2}$. By improving a previous result of Amano (2014), where an upper bound $\bp{K_n}{1.5}\Leq n^{2/3}$ was proved, Shigeta and Amano (2015) proved an almost optimal upper bound $\bp{K_n}{1.5}\leq n^{1/2+o(1)}$.

Partial partitions of matrices

The adjacency matrix of $K_n$ is the complement $\overline{I_n}$ of the identity matrix $_n$. So, in terms of Boolean matrices, the upper bound $\bp{K_n}{1.5}\leq n^{1/2+o(1)}$ of Shigeta and Amano (2015) result translates to the claim that the matrix $\overline{I_n}$ has a "partial decomposition" into at most $n^{1/2+o(1)}$ rectangles. Here, a partial decomposition of a symmetric matrix $A$ as a collection of pairwise disjoint rectangles in (all-$1$ submatrices of) $A$ with the following property: for every $1$-entry $(i,j)$ of $A$, either $(i,j)$ or $(j,i)$ is a $1$-entry in at least one of the rectangles. That is, the rectangles now do not need to cover all $1$-entries of $A$, but for every $1$-entry either this entry or its "symmetric copy" (w.r.t. to the diagonal) must be covered.

We thus have the following

Theorem 1 (Shigeta and Amano): The complement $\overline{I_m}$ of the identity $m\times m$ matrix $I_m$ has a partial decomposition $R_1,\ldots,R_t$ into $t\leq m^{1/2+o(1)}$ rectangles.

Using Theorem 1, it is easy to construct matrices $A$ with $\Dec{A}{0}\gg \Dec{A}{1}$.

Theorem 2: There exist $n\times n$ matrices $A$ such that $\Dec{A}{1}\leq n^{1/2+o(1)}$ but $\Dec{A}{0}=n$. Hence, \[ \Dec{A}{0}\geq \Dec{A}{1}^{2-o(1)}\,. \]
Proof: Let $R_1,\ldots,R_t$ be a partial decomposition of $\overline{I_n}$ into $t\leq n^{1/2+o(1)}$ rectangles, and consider the $n\times n$ matrix $A$ with $A[i,j]=1$ iff $R_\ell[i,j]=1$ for some $\ell\in\{1,\ldots,t\}$. Thus, $A$ is obtained from the matrix $\overline{I_n}$ by switching to $0$ some its $1$-entries (those not covered by the rectangles). Below is an example of a partial decomposition of $\overline{I_6}$ into $4$ rectangles $R_1=\{1,2\}\times\{4,6\}$ ($\bullet$), $R_2=\{1,3\}\times\{2,5\}$ ($\ast$), $R_3=\{3,6\}\times\{1,4\}$ ($\Box$) and $R_4=\{2,4,6\}\times\{3,5\}$ ($\diamond$), and the resulting matrix $A$:

\[ \mathrm{Rectangles} = \begin{bmatrix} {\bf 0} & \ast & . & \bullet & \ast & \bullet\\ . & {\bf 0} & \diamond & \bullet & \diamond & \bullet\\ \Box & \ast & {\bf 0} & \Box & \ast & . \\ . & . & \diamond & {\bf 0} & \diamond & . \\ . & . & . & . & {\bf 0} & . \\ \Box & . & \diamond & \Box & \diamond & {\bf 0} \end{bmatrix}\qquad A=\begin{bmatrix} {\bf 0} & 1 & 0 & 1 & 1 & 1\\ 0 & {\bf 0} & 1 & 1 & 1 & 1\\ 1 & 1 & {\bf 0} & 1 & 1 & 0 \\ 0 & 0 & 1 & {\bf 0} & 1 & 0 \\ 0 & 0 & 0 & 0 & {\bf 0} & 0 \\ 1& 0 & 1 & 1 & 1 & {\bf 0} \end{bmatrix} \]

The partial decomposition $R_1,\ldots,R_t$ into $t\leq n^{1/2+o(1)}$ rectangles of $\overline{I_n}$ gives us a partition of all $1$-entries of $A$ into $t\leq n^{1/2+o(1)}$ pairwise disjoint rectangles; so, $\Dec{A}{1}\leq n^{1/2+o(1)}$.

On the other hand, the matrix $A$ has the following property: for every two distinct $0$-entries $(i,i)$ and $(j,j)$ on the diagonal, at least one of $(i,j)$ or $(j,i)$ is a $1$-entry of $A$. Thus, the complement matrix $\oA$ has a fooling set of size $m$: no two $1$-entries of the diagonal of $\oA$ can belong to the same all-$1$ matrix. Thus, $\Dec{A}{0}=\Dec{\oA}{1}=n$. $\Box$

Remark: The SUM-complexity of a Boolean matrix $A$ is the minimum number of fanin-two addition $(+)$ gates sufficient to compute the the operator $f(x)=Ax$ over the semigroup $(\NN,+)$. In this comment the matrix from Theorem 2 is used to show that the SUM-complexity of an $n\times n$ matrix can be by a factor of $n^{1/4-o(1)}$ larger than the SUM-complexity of its complement.

A super-polynomial gap

By Theorem 2, partitioning $0$-entries of some matrices may be quadratically more expensive than partitioning their $1$-entries, and the result of Alon (1997) implies that no larger gaps can be achieved using partial decompositions. Much larger gaps follow from the recent lower bounds on the nondeterministic communication complexity of the CIS (clique vs independent set) problem.

For a given graph $G$ on $v$ vertices, a CIS-intersection matrix $A_G$ is constructed in the following way. The rows are labeled by cliques, and columns by independent sets of $G$, and $A_G[a,b]=|a\cap b|$. That is, the $0$s of $A_G$ correspond to disjoint pairs $(a,b)$, and $1$s to pairs $(a,b)$ sharing a common vertex.

Clearly, $\Dec{A_G}{1} \leq v$, since all $1$s of $A_G$ may be partition into $v$ rectangles $R_1,\ldots,R_v$ with $R_i=\{(a,b)\colon i\in a\cap b\}$. By \eqref{eq:2}, we have $\log \Dec{A_G}{0}\Leq \log^2 v$. But it was long unknown whether $\log \Dec{A_G}{0}$ can be much larger than $\log v$. In a series of works, existence of $v$-vertex graphs $G$ with $\log \Dec{A_G}{0}\Geq \log^{2-c} v$ for smaller and smaller values of $c$ where shown: $c=0.872$ (Göös 2015), $c=0.5+o(1)$ (Ben-David et al. 2021) and $c=o(1)$ (Balodis 2021).

These results imply that the gap between $\Dec{A}{0}$ and $\Dec{A}{1}$ can be even super-polynomial.

Theorem 3: There exist matrices $A$ such that \[ \log \Dec{A}{0}\Geq \log^{2-o(1)}\Dec{A}{1}\,. \]
By \eqref{eq:2}, this lower bound is essentially tight (in terms of $\Dec{A}{1}$).

Proof: Take a graph $G=(V,E)$ whose existence is is shown by Balodis (2021), and let $v=|V|$. For the corresponding clique-independent set matrix $A_G$, we then have $\log \Dec{A_G}{1} \leq \log v$ and $\Dec{A_G}{0} \Geq \log^{1+c} v$ with $c=1-o(1)$. Cliques and independent set of $G$ are subsets of $V$. So, $A_G$ is a $2^r\times 2^s$ matrix with $r,s\leq v$. Turn the matrix $A_G$ into a square $n \times n$ matrix $A$ with $n=2^v$ by duplicating some rows or columns: this affects neither $\Dec{A}{0}$ nor $\Dec{A}{1}$. Thus, $\log \Dec{A}{1}= \log\Dec{A_G}{1}\leq \log v$ but $\log \Dec{A}{0}=\log \Dec{A_G}{0}\Geq \log^{2-o(1)}\Dec{A}{1}$. $\Box$

In terms of the dimension $n$ of $n\times n$ matrices $A$, the gaps given by Theorems 2 and 3 are as follows:


  1. A.V. Aho, J.D. Ullman, M. Yannakakis (1983). On notions of information transfer in VLSI circuits. Proc. 15th STOC, 133-139. local copy
  2. Alon N. (1997), Neighborly Families of Boxes and Bipartite Coverings. In: Graham R.L., Nešetril J. (eds) The Mathematics of Paul Erdős II. Algorithms and Combinatorics, vol 14. Springer, Berlin, Heidelberg. doi: 10.1007/978-3-642-60406-5_3. Manuscript
  3. K. Amano (2014), Some improved bounds on communication complexity via new decomposition of cliques. Discrete Appl. Math., Vol. 166, 249-254. doi: 10.1016/j.dam.2013.09.015
  4. K. Balodis (2021), Several separations based on a partial Boolean function. arXiv:2103.05593 [added March 2021]
  5. S. Ben-David, M. Göös, S. Jain and R. Kothari (2021), Unambiguous DNF from Hex. arXiv:2102.08348
  6. M. Göös (2015). Lower bounds for clique vs. independent set. Proc. 56th FOCS, 1066-1076.
  7. M. Göös, T. Pitassi and T. Watson (2018). Deterministic Communication vs. Partition Number. SIAM J. Comput. 47(6), 2435-2450. ECCC report.
  8. R. L. Graham and H. O. Pollak (1971): On the addressing problem for loop switching, Bell Syst. Tech. J. 50, 2495-2519. See here for a linear algebra proof by Trevberg.
  9. E. Kushilevitz, N. Linial and R. Ostrovsky (1999). The linear-array conjecture in communication complexity is false. Combinatorica, 19(2):241-254. doi: 10.1007/s004930050054.
  10. M. Shigeta and K. Amano (2015), Ordered biclique partitions and communication complexity problems. Discrete Appl. Math., Vol. 184, 248-252. doi: 10.1016/j.dam.2014.10.029.
  11. M. Yannakakis (1991): Expressing combinatorial optimization problems by linear programs, J. Comput. Syst. Sci. 43, 441-466. local copy.

S. Jukna
February 5, 2021