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?

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}Question: Can $\Dec{A}{0}$ be much larger than $\Dec{A}{1}$?

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)}\,. \]

\[ \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.

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

- Theorem 2: $\Dec{A}{0}/\Dec{A}{1}\Geq n^{1/2-o(1)}$; matrix $A$ explicit.
- Theorem 3: $\Dec{A}{0}/\Dec{A}{1}\Geq (\log n)^{\alpha}$ for $\alpha=(\log\log n)^{2-o(1)}-1$; matrix $A$ not explicit (existence only).

**References:**

- A.V. Aho, J.D. Ullman, M. Yannakakis (1983). On notions of information transfer in VLSI circuits. Proc. 15th STOC, 133-139. local copy
- 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
- 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 - K. Balodis (2021), Several separations based on a partial Boolean function. arXiv:2103.05593 [added March 2021]
- S. Ben-David, M. Göös, S. Jain and R. Kothari (2021), Unambiguous DNF from Hex. arXiv:2102.08348
- M. Göös (2015). Lower bounds for clique vs. independent set. Proc. 56th FOCS, 1066-1076.
- M. Göös, T. Pitassi and T. Watson (2018).
Deterministic Communication vs. Partition Number.
*SIAM J. Comput.*47(6), 2435-2450. ECCC report. - 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. - 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. - 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. - M. Yannakakis (1991): Expressing combinatorial optimization problems by linear programs, J. Comput. Syst. Sci. 43, 441-466. local copy.

S. Jukna

February 5, 2021