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.
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)}$.
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.
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:
References: