#  On the Binary and Boolean Rank of Regular Matrices

Ishay Haviv School of Computer Science, The Academic College of Tel Aviv-
Yaffo, Tel Aviv 61083, Israel. Research supported in part by the Israel
Science Foundation (grant No. 1218/20). Michal Parnas School of Computer
Science, The Academic College of Tel Aviv-Yaffo, Tel Aviv 61083, Israel. Email
address<EMAIL_ADDRESS>
###### Abstract

A $0,1$ matrix is said to be regular if all of its rows and columns have the
same number of ones. We prove that for infinitely many integers $k$, there
exists a square regular $0,1$ matrix with binary rank $k$, such that the
Boolean rank of its complement is $k^{\widetilde{\Omega}(\log k)}$.
Equivalently, the ones in the matrix can be partitioned into $k$ combinatorial
rectangles, whereas the number of rectangles needed for any cover of its zeros
is $k^{\widetilde{\Omega}(\log k)}$. This settles, in a strong form, a
question of Pullman (Linear Algebra Appl., 1988) and a conjecture of Hefner,
Henson, Lundgren, and Maybee (Congr. Numer., 1990). The result can be viewed
as a regular analogue of a recent result of Balodis, Ben-David, Göös, Jain,
and Kothari (FOCS, 2021), motivated by the clique vs. independent set problem
in communication complexity and by the (disproved) Alon-Saks-Seymour
conjecture in graph theory. As an application of the produced regular
matrices, we obtain regular counterexamples to the Alon-Saks-Seymour
conjecture and prove that for infinitely many integers $k$, there exists a
regular graph with biclique partition number $k$ and chromatic number
$k^{\widetilde{\Omega}(\log k)}$.

##  1 Introduction

For a $0,1$ matrix $M$ of dimensions $n\times m$, consider the following three
notions of rank.

  * •

The (standard) rank of $M$ over $\mathbb{R}$, denoted by
${\mathop{\mathrm{rank}}}_{\mathbb{R}}(M)$, is the minimal $k$ for which there
exist real matrices $A$ and $B$ of dimensions $n\times k$ and $k\times m$
respectively, such that $M=A\cdot B$ where the operations are over
$\mathbb{R}$.

  * •

The binary rank of $M$, denoted by
${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)$, is the minimal $k$ for which
there exist $0,1$ matrices $A$ and $B$ of dimensions $n\times k$ and $k\times
m$ respectively, such that $M=A\cdot B$ where the operations are over
$\mathbb{R}$. Equivalently, ${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)$ is
the smallest number of monochromatic combinatorial rectangles111A
(combinatorial) rectangle in a matrix $M$ is a set $P\times Q$, where $P$ and
$Q$ are sets of rows and columns in $M$ respectively. The rectangle is said to
be monochromatic if the entries of the corresponding submatrix of $M$ are all
equal. in a partition of the ones in $M$.

  * •

The Boolean rank of $M$, denoted by
${\mathop{\mathrm{rank}}}_{\mathbb{B}}(M)$, is the minimal $k$ for which there
exist $0,1$ matrices $A$ and $B$ of dimensions $n\times k$ and $k\times m$
respectively, such that $M=A\cdot B$ where the operations are under Boolean
arithmetic (namely, $0+x=x+0=x$, $1+1=1\cdot 1=1$, and $x\cdot 0=0\cdot x=0$).
Equivalently, ${\mathop{\mathrm{rank}}}_{\mathbb{B}}(M)$ is the smallest
number of monochromatic combinatorial rectangles in a cover of the ones in
$M$.

Note that the binary rank and the Boolean rank are sometimes referred to in
the literature as the $1$-partition number and the $1$-cover number
respectively. Note further that every $0,1$ matrix $M$ satisfies
${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)\geq{\mathop{\mathrm{rank}}}_{\mathbb{R}}(M)$
and
${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)\geq{\mathop{\mathrm{rank}}}_{\mathbb{B}}(M)$.

The above notions of rank play a central role in the area of communication
complexity, introduced in 1979 by Yao [31]. In the communication problem
associated with a $0,1$ matrix $M$ of dimensions $n\times m$, one player holds
a row index $i\in[n]$ and another player holds a column index $j\in[m]$, and
their goal is to decide whether $M_{i,j}=1$ while minimizing the worst-case
number of communicated bits. For the deterministic setting, the well-known
log-rank conjecture of Lovász and Saks [24] suggests that the communication
complexity of the problem is polynomially related to
$\log_{2}{\mathop{\mathrm{rank}}}_{\mathbb{R}}(M)$ (see, e.g., [25]). For the
non-deterministic setting, it is not difficult to see that the minimum number
of bits that should be communicated is precisely
$\lceil\log_{2}{\mathop{\mathrm{rank}}}_{\mathbb{B}}(M)\rceil$. For the
unambiguous non-deterministic setting, where each input is required to have at
most one accepting computation, the minimum number of bits that should be
communicated is precisely
$\lceil\log_{2}{\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)\rceil$.

For a $0,1$ matrix $M$, let $\overline{M}$ denote the complement matrix
obtained from $M$ by replacing the ones by zeros and the zeros by ones. A
result of Yannakakis [30] implies that every $0,1$ matrix $M$ with
${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)=k$ satisfies

$\displaystyle{\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})\leq{\mathop{\mathrm{rank}}}_{\mathrm{bin}}(\overline{M})\leq
k^{O(\log k)}.$ (1)

The challenge of determining the largest possible value of
${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})$ for a $0,1$ matrix $M$
with ${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)=k$ has attracted intensive
attention in the literature, mostly with the equivalent formulation of the
clique vs. independent set problem introduced in [30] (see [20, Chapter 4.4]).
The first non-trivial bound was given by Huang and Sudakov [19] who provided,
building on a construction of Razborov [28], a family of such matrices $M$
satisfying
${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})\geq\Omega(k^{6/5})$ (see
[11] for extended constructions). The constant $6/5$ in the exponent was
improved to $3/2$ by Amano [1] and then to $2$ by Shigeta and Amano [29]. The
first super-polynomial separation was obtained by Göös [13], who provided a
family of such matrices $M$ satisfying
${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})\geq
k^{\Omega(\log^{0.128}k)}$. This was then improved in a work of Ben-David,
Hatami, and Tal [3] to
${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})\geq
k^{\Omega(\log^{0.22}k)}$. In a recent breakthrough, it was shown by Balodis,
Ben-David, Göös, Jain, and Kothari [2] that the bound can be further improved
to ${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})\geq
k^{\widetilde{\Omega}(\log k)}$, which matches the upper bound in (1) up to
$\log\log k$ factors hidden in the $\widetilde{\Omega}$ notation. Note that
the result of [2] strengthens an earlier result of Göös, Pitassi, and Watson
[15], who provided a near optimal separation between the binary rank of a
$0,1$ matrix and the deterministic communication complexity of the problem
associated with it.

Interestingly, the above problem is closely related to a graph-theoretic
problem proposed by Alon, Saks, and Seymour in 1991 (see [21]). For a graph
$G$, let $\chi(G)$ denote its chromatic number, and let
$\mathop{\mathrm{bp}}(G)$ denote its biclique partition number, that is, the
smallest number of edge-disjoint bicliques (i.e., complete bipartite graphs)
needed for a partition of the edge set of $G$. A classic result of Graham and
Pollak [16] asserts that the complete graph $K_{n}$ on $n$ vertices satisfies
$\mathop{\mathrm{bp}}(K_{n})=n-1$. Inspired by this result, Alon, Saks, and
Seymour conjectured that every graph $G$ satisfies
$\mathop{\mathrm{bp}}(G)\geq\chi(G)-1$. The conjecture was disproved by Huang
and Sudakov in [19], where it was shown that for infinitely many integers $k$
there exists a graph $G$ satisfying $\mathop{\mathrm{bp}}(G)=k$ and
$\chi(G)\geq\Omega(k^{6/5})$. These graphs were used there to derive the
aforementioned separation between ${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)$
and ${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})$ for $0,1$ matrices
$M$ (see [19, Section 4]). In a work of Bousquet, Lagoutte, and Thomassé [6],
the two problems were shown to be essentially equivalent, allowing the authors
of [2] to derive, for infinitely many integers $k$, the existence of a graph
$G$ satisfying $\mathop{\mathrm{bp}}(G)=k$ and $\chi(G)\geq
k^{\widetilde{\Omega}(\log k)}$. As in the matrix setting, the gap is optimal
up to $\log\log k$ factors in the exponent.

A $0,1$ matrix $M$ is said to be $d$-regular if every row and every column in
$M$ has precisely $d$ ones. In 1986, Brualdi, Manber, and Ross [7] proved that
for every $d$-regular $0,1$ matrix $M$ of dimensions $n\times n$ where
$0<d<n$, the rank of $M$ over the reals is equal to that of its complement,
that is,
${\mathop{\mathrm{rank}}}_{\mathbb{R}}(M)={\mathop{\mathrm{rank}}}_{\mathbb{R}}(\overline{M})$.
Following their work, Pullman [27] asked in 1988 whether every such matrix $M$
satisfies
${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)={\mathop{\mathrm{rank}}}_{\mathrm{bin}}(\overline{M})$.
In 1990, Hefner, Henson, Lundgren, and Maybee [18] conjectured that the answer
to this question is negative (see [18, Conjecture 3.2]). The question was
asked again in 1995 in a survey by Monson, Pullman, and Rees [26] (see [26,
Open problem 7.1]).222The question of [27, 18, 26] was originally formulated
using the notion of non-negative integer rank, which coincides with the binary
rank for $0,1$ matrices (see, e.g., [17, Lemma 2.1]). Note that for the
Boolean rank, such a statement does not hold in general. For example, the
$1$-regular identity matrix $I_{n}$ satisfies
${\mathop{\mathrm{rank}}}_{\mathbb{B}}(I_{n})=n$ and yet
${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{I_{n}})=(1+o(1))\cdot\log_{2}n$
(see [12]).

###  1.1 Our Contribution

The current work aims to determine the largest possible gap between the binary
rank of regular $0,1$ matrices and the Boolean rank of their complement. Our
main result is the following.

######  Theorem 1.1.

For infinitely many integers $k$, there exists a square regular $0,1$ matrix
$M$ satisfying

${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)=k\mbox{~{}~{}~{}and~{}~{}~{}}{\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})\geq
k^{\widetilde{\Omega}(\log k)}.$

Theorem 1.1 can be viewed as a regular analogue of the aforementioned result
of Balodis et al. [2], showing that their near optimal separation between
${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)$ and
${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})$, which is achieved by
irregular matrices $M$, can also be attained by regular ones. Since every
$0,1$ matrix $M$ satisfies
${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(\overline{M})\geq{\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})$,
Theorem 1.1 settles, in a strong form, the question of Pullman asked in [27,
26] (and the variants of the question mentioned there) and confirms the
conjecture of Hefner et al. [18]. We remark that regular matrices $M$ with
${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})$ larger than
${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)$ can also be derived from [19]
(see Section 1.2 for details). While these matrices are sufficient to answer
the original question of [27, 26], they only achieve a polynomial gap between
the quantities.

The proof of Theorem 1.1 relies on a modification of the construction of [2]
to the regular setting. It involves an extension of the query-to-communication
lifting theorem in non-deterministic communication complexity proved by Göös,
Lovett, Meka, Watson, and Zuckerman [14], as well as a two-source extractor
studied by Bouda, Pivoluska, and Plesch [4] and by Kothari, Meka, and
Raghavendra [22]. For an overview of the proof, see Section 1.2.

As alluded to before, matrices $M$ with
${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)$ much smaller than
${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})$ are known to imply
graphs $G$ with $\mathop{\mathrm{bp}}(G)$ much smaller than $\chi(G)$, and
thus yield counterexamples to the Alon-Saks-Seymour conjecture (see [6]).
Although the conjecture is false in general, it is of interest to identify
classes of graphs that satisfy a polynomial version of the conjecture. In
particular, it was asked in [2] whether the chromatic number of perfect graphs
is polynomially upper bounded in terms of their biclique partition number (see
[30] for a related question; see also [23, 5, 10]). As an application of
Theorem 1.1, we show that this is not the case for the class of regular
graphs. Namely, we show that the near optimal separation achieved in [2]
between the biclique partition number and the chromatic number can also be
attained by regular graphs.

######  Theorem 1.2.

For infinitely many integers $k$, there exists a simple regular graph $G$
satisfying

${\mathop{\mathrm{bp}}}(G)=k\mbox{~{}~{}~{}and~{}~{}~{}}\chi(G)\geq
k^{\widetilde{\Omega}(\log k)}.$

###  1.2 Overview of Proofs

Our goal is to obtain regular $0,1$ matrices $M$ for which the binary rank of
$M$ is much smaller than the Boolean rank of $\overline{M}$. We first observe
that a polynomial gap between the two quantities, for a regular matrix, can be
derived from a construction of Huang and Sudakov [19]. Indeed, it can be
verified that the (simple) graphs $G$ given in [19], which satisfy
$\mathop{\mathrm{bp}}(G)=k$ and $\chi(G)\geq\Omega(k^{6/5})$, are regular,
hence their adjacency matrices are regular as well. The following simple claim
implies that these adjacency matrices achieve a polynomial gap between the
binary rank and the Boolean rank of the complement.

######  Claim 1.3.

For every simple graph $G$, the adjacency matrix $M$ of $G$ satisfies

${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)\leq
2\cdot\mathop{\mathrm{bp}}(G)~{}~{}~{}\mbox{and}~{}~{}~{}{\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})\geq\chi(G).$

  * Proof:

For a simple graph $G$ on the vertex set $[n]$, put
$k=\mathop{\mathrm{bp}}(G)$, and let $(A_{1},B_{1}),\ldots,(A_{k},B_{k})$ be
the $k$ bipartitions of the $k$ edge-disjoint bicliques that form a partition
of the edge set of $G$. Observe that for every $i\in[k]$, the sets
$A_{i}\times B_{i}$ and $B_{i}\times A_{i}$ form combinatorial rectangles of
ones in the adjacency matrix $M$ of $G$, and that these $2k$ rectangles form a
partition of the ones in $M$, hence
${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)\leq 2\cdot k$.

Next, put $m={\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})$, and let
$A_{1}\times B_{1},\ldots,A_{m}\times B_{m}$ be $m$ combinatorial rectangles
that form a cover of the ones in $\overline{M}$, i.e., the zeros in $M$. For
every $i\in[m]$, let $C_{i}$ denote the set of elements $j\in[n]$ satisfying
$(j,j)\in A_{i}\times B_{i}$. Since $G$ is simple, the elements on the
diagonal of $M$ are all zeros, hence the sets $C_{i}$ for $i\in[m]$ cover all
vertices of $G$. Since $A_{i}\times B_{i}$ is a rectangle of zeros in $M$, it
also follows that $C_{i}$ is an independent set in $G$. This implies that
$m\geq\chi(G)$, and we are done.

The matrices $M$ that are known to achieve super-polynomial separations
between ${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)$ and
${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})$, however, are apparently
far from being regular [13, 3, 2]. Their constructions rely on a powerful
technique, known as query-to-communication lifting, that enables to deduce
separation results in communication complexity from separation results in the
more approachable area of query complexity. The proofs of the separation
results of [13, 3, 2] involve two main steps, as described below.

In the first step, one provides a family of Boolean functions
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ with a large gap between two certain
measures of Boolean functions, namely, the unambiguous $1$-certificate
complexity of $f$ and the $0$-certificate complexity of $f$ (see Section 2.3).
These measures can be viewed as query complexity analogues of the binary rank
of a matrix and the Boolean rank of its complement. It is shown in [2] that
the gap between the two measures can be nearly quadratic.

In the second step, the separation is “lifted” from query complexity to
communication complexity. This is done by considering, for some gadget
function $g:\\{0,1\\}^{\ell}\times\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}$, the
communication problem in which two players get inputs from
$\\{0,1\\}^{\ell\cdot n}$ and aim to determine the value of the composed
function $f\circ g^{n}:\\{0,1\\}^{\ell\cdot n}\times\\{0,1\\}^{\ell\cdot
n}\rightarrow\\{0,1\\}$, defined by

$(f\circ g^{n})(x,y)=f(g(x_{1},y_{1}),g(x_{2},y_{2}),\ldots,g(x_{n},y_{n}))$

for all $x,y\in\\{0,1\\}^{\ell\cdot n}$. Here, the vectors
$x=(x_{1},\ldots,x_{n})$ and $y=(y_{1},\ldots,y_{n})$ are viewed as
concatenations of $n$ blocks of size $\ell$. Query-to-communication lifting
results typically show that for some gadget $g$, a gap between certain query
complexity measures of $f$ implies a gap between the suitable communication
complexity measures of the composed function $f\circ g^{n}$. For the non-
deterministic setting, it is shown in [14] that if the gadget $g$ is the inner
product function on vectors of length $\ell=\Theta(\log n)$, then a gap
between the unambiguous $1$-certificate complexity and the $0$-certificate
complexity for $f$ implies a gap between the unambiguous non-deterministic
communication complexity and the co-non-deterministic communication complexity
for $f\circ g^{n}$ (see also [13, Appendix A]). The analysis uses the fact
that the inner product function forms a two-source extractor, as shown by Chor
and Goldreich [9].

Let $M$ denote the matrix associated with the communication problem of $f\circ
g^{n}$ for the function $f$ constructed in [2] and the inner product function
$g$. The lifting result of [14] implies that $M$ attains a near optimal
separation between ${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)$ and
${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})$. However, it can be seen
that the matrix $M$ is not regular at all. For example, the row and the column
of $M$ that correspond to the all-zero vector consist of only ones or only
zeros, depending on the value of $f$ on the all-zero vector.

We turn to describe how we obtain regular matrices $M$ with a similar gap
between ${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)$ and
${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})$. We first observe that
to construct a regular matrix $M$, it suffices to replace the inner product
function in the above construction by a different gadget function $g$.
Specifically, it turns out that if $g$ is unbiased in a strong sense, namely,
it is unbiased even while fixing one of its two inputs, then the matrix $M$
associated with $f\circ g^{n}$ is regular for any function $f$ (see Section
4.1). Hence, to obtain the desired separation on regular matrices, we provide
an extension of the query-to-communication lifting theorem of [14] which
allows the gadget function $g$ to be not only the inner product function but
any low-discrepancy function. We note that such an extension was speculated
already in [14, Remark 1] and was actually established for the deterministic
and probabilistic settings in a recent work of Chattopadhyay, Filmus, Koroth,
Meir, and Pitassi [8]. Building on the approach of [14] and on tools supplied
in [8], we prove that such an extension holds for the non-deterministic
setting as well (for a precise statement, see Theorem 3.2). We proceed by
showing that a slight variant $g$ of the inner product function, studied in
[4] and in [22], is unbiased in the required sense and has low discrepancy.
Then, to prove Theorem 1.1, we apply our generalized query-to-communication
lifting theorem to the family of functions $f$ provided in [2] with this
gadget $g$.

Let us mention that our generalized lifting theorem is not essential for the
proof of Theorem 1.1. It turns out that the matrix $M$ obtained using the
aforementioned gadget function $g$ has a sub-matrix that corresponds to a
composition with the standard inner product function, hence the lower bound on
${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})$ can also be derived from
the lifting result of [14]. Yet, the generality of our lifting theorem, proved
in Appendix A, can be used to obtain a separation between
${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)$ and
${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})$ using various other
gadget functions, and we believe that it might find additional applications.

We finally use the regular matrices given in Theorem 1.1 to provide regular
counterexamples for the Alon-Saks-Seymour conjecture and to prove Theorem 1.2.
It is shown in [6] that a matrix $M$ with
${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)$ much smaller than
${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})$ can be transformed into
a graph $G$ with $\mathop{\mathrm{bp}}(G)$ much smaller than $\chi(G)$. This
transformation, however, does not preserve the regularity. In fact, a natural
attempt to produce a regular graph $G$ from a regular matrix $M$ using the
approach of [6] results in a graph that is not even simple (because it has
loops). Moreover, certain steps of the argument of [6] identify subgraphs of
this graph $G$ with a biclique partition number much smaller than the
chromatic number, but those subgraphs are not necessarily regular even if $G$
is. We overcome these difficulties by combining the approach of [6] with a
couple of additional ideas, and show that any square regular matrix $M$ with a
large gap between ${\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)$ and
${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})$ can be transformed into
a simple regular graph $G$ with a similar gap between
$\mathop{\mathrm{bp}}(G)$ and $\chi(G)$ (see Theorem 5.1).

###  1.3 Outline

The rest of the paper is organized as follows. In Section 2, we collect
several definitions and results needed throughout the paper. In Section 3, we
present our generalized query-to-communication lifting theorem in non-
deterministic communication complexity. Its proof is given in Appendix A. In
Section 4, we present and analyze a certain gadget function, and combine it
with the lifting theorem to prove Theorem 1.1. Finally, in Section 5, we
obtain regular graphs that form counterexamples to the Alon-Saks-Seymour
conjecture and confirm Theorem 1.2.

##  2 Preliminaries

###  2.1 Non-deterministic Communication Complexity

Let $\Lambda$ be a finite set, and let
$F:\Lambda\times\Lambda\rightarrow\\{0,1\\}$ be a function. In the
communication problem associated with $F$, one player holds an input
$x\in\Lambda$ and another player holds an input $y\in\Lambda$, and their goal
is to decide whether $F(x,y)=1$ by a communication protocol that minimizes the
worst-case number of communicated bits. The $0,1$ matrix $M$ associated with
the function $F$ is the matrix whose rows and columns are indexed by
$\Lambda$, defined by $M_{x,y}=F(x,y)$ for all $x,y\in\Lambda$. Consider the
following three non-deterministic communication complexity measures of a
function $F$.

  * •

The non-deterministic communication complexity of $F$, denoted by
$\mathsf{NP^{cc}}(F)$, is the smallest possible number of communicated bits in
a non-deterministic communication protocol for $F$, that is, a protocol
satisfying that $F(x,y)=1$ if and only if there exists an accepting
computation on $(x,y)$. It holds that
$\mathsf{NP^{cc}}(F)=\lceil\log_{2}{\mathop{\mathrm{rank}}}_{\mathbb{B}}(M)\rceil$.

  * •

The co-non-deterministic communication complexity of $F$, denoted by
$\mathsf{coNP^{cc}}(F)$, is the non-deterministic communication complexity of
the negation $\neg F$ of $F$, defined by $(\neg F)(x,y)=1-F(x,y)$ for all
$x,y\in\Lambda$. It thus holds that
$\mathsf{coNP^{cc}}(F)=\lceil\log_{2}{\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})\rceil$.

  * •

A non-deterministic protocol is called unambiguous if it satisfies that each
input has at most one accepting computation. The smallest possible number of
communicated bits in such a protocol for $F$ is referred to as the unambiguous
non-deterministic communication complexity of $F$ and is denoted by
$\mathsf{UP^{cc}}(F)$. It holds that
$\mathsf{UP^{cc}}(F)=\lceil\log_{2}{\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)\rceil$.

###  2.2 Composed Functions

For integers $n$ and $\ell$, let $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and
$g:\\{0,1\\}^{\ell}\times\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}$ be two
functions. The function $g^{n}:\\{0,1\\}^{\ell\cdot
n}\times\\{0,1\\}^{\ell\cdot n}\rightarrow\\{0,1\\}^{n}$ is defined by

$g^{n}(x,y)=(g(x_{1},y_{1}),g(x_{2},y_{2}),\ldots,g(x_{n},y_{n}))$

for all $x,y\in\\{0,1\\}^{\ell\cdot n}$, where the vectors
$x=(x_{1},\ldots,x_{n})$ and $y=(y_{1},\ldots,y_{n})$ are viewed as
concatenations of $n$ blocks of size $\ell$. The composed function $f\circ
g^{n}:\\{0,1\\}^{\ell\cdot n}\times\\{0,1\\}^{\ell\cdot
n}\rightarrow\\{0,1\\}$ is defined by

$(f\circ g^{n})(x,y)=f(g^{n}(x,y)).$

For a set $I\subseteq[n]$ and a vector $x\in\\{0,1\\}^{\ell\cdot n}$, we let
$x_{I}\in\\{0,1\\}^{\ell\cdot|I|}$ denote the projection of $x$ to the blocks
whose indices are in $I$. Note that when $I=\\{i\\}$ for some $i\in[n]$, we
have $x_{i}=x_{I}$. For vectors $x,y\in\\{0,1\\}^{\ell\cdot n}$, we let
$g^{I}(x_{I},y_{I})$ denote the projection of $g^{n}(x,y)$ to the indices of
$I$.

###  2.3 Certificate Complexity

An $n$-variate $k$-DNF formula $\varphi$ is a Boolean formula on $n$ variables
that can be written as a disjunction $\varphi=c_{1}\vee\cdots\vee c_{m}$,
where every $c_{i}$ is a conjunction of at most $k$ literals. The formula
$\varphi$ is said to be unambiguous if for every input $x\in\\{0,1\\}^{n}$
there is at most one $i\in[m]$ that satisfies $c_{i}(x)=1$. For a Boolean
function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, consider the following query
complexity measures.

  * •

The $1$-certificate complexity of $f$, denoted by $\mathsf{C}_{1}(f)$, is the
smallest integer $k$ for which $f$ can be written as a $k$-DNF formula.

  * •

The $0$-certificate complexity of $f$, denoted by $\mathsf{C}_{0}(f)$, is
$\mathsf{C}_{1}(\neg f)$, where $\neg f$ is the negation of $f$. Equivalently,
$\mathsf{C}_{0}(f)$ is the smallest integer $k$ for which $f$ can be written
as a $k$-CNF formula.

  * •

The unambiguous $1$-certificate complexity of $f$, denoted by
$\mathsf{UC}_{1}(f)$, is the smallest integer $k$ for which $f$ can be written
as an unambiguous $k$-DNF formula.

We need the following result that was proved in [2].

######  Theorem 2.1 ([2]).

For infinitely many integers $r$, there exists a Boolean function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ satisfying $\mathsf{UC}_{1}(f)=r$ and
$\mathsf{C}_{0}(f)\geq\widetilde{\Omega}(r^{2})$ where $r=n^{\Omega(1)}$.

###  2.4 Discrepancy

######  Definition 2.2 (Discrepancy with respect to the uniform distribution).

Let $\Lambda$ be a finite set, and let
$g:\Lambda\times\Lambda\rightarrow\\{0,1\\}$ be a function. Let $X,Y$ be
independent random variables that are uniformly distributed over $\Lambda$.
The discrepancy of $g$ (with respect to the uniform distribution) on a
combinatorial rectangle $R\subseteq\Lambda\times\Lambda$ is denoted by
$\mathop{\mathrm{disc}}_{R}(g)$ and is defined by

${\mathop{\mathrm{disc}}}_{R}(g)=\Big{|}{\Pr\left[{g(X,Y)=0\mbox{~{}and~{}}(X,Y)\in
R}\right]}-{\Pr\left[{g(X,Y)=1\mbox{~{}and~{}}(X,Y)\in R}\right]}\Big{|}.$

The discrepancy of $g$, denoted by $\mathop{\mathrm{disc}}(g)$, is defined as
the maximum of $\mathop{\mathrm{disc}}_{R}(g)$ over all combinatorial
rectangles $R\subseteq\Lambda\times\Lambda$.

##  3 Lifting from Certificate to Communication Complexity

In this section, we present our extension of the query-to-communication
lifting theorem in non-deterministic communication complexity to general low-
discrepancy functions. We start with a simple upper bound on the unambiguous
non-deterministic communication complexity of a composed function.

######  Lemma 3.1.

For all functions $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and
$g:\\{0,1\\}^{\ell}\times\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}$, it holds that

$\mathsf{UP^{cc}}(f\circ g^{n})\leq
O\big{(}\mathsf{UC}_{1}(f)\cdot\max(\log_{2}n,\ell)\big{)}.$

  * Proof:

Put $k=\mathsf{UC}_{1}(f)$. Then, the function $f$ can be written as an
unambiguous $n$-variate $k$-DNF formula $\varphi=c_{1}\vee\cdots\vee c_{m}$
where $m\leq(2n)^{k}$. Consider the following non-deterministic protocol for
the communication problem associated with the function $f\circ g^{n}$. Let
$x,y\in\\{0,1\\}^{\ell\cdot n}$ be the inputs of the players. The first player
selects non-deterministically an index $i\in[m]$ and sends it to the other
player. Let $I\subseteq[n]$ denote the set of indices of the variables that
appear in the clause $c_{i}$, and note that $|I|\leq k$. Then, the first
player sends the projection $x_{I}$ of $x$ to the blocks of $I$, and
similarly, the second player sends the projection $y_{I}$ of $y$ to the blocks
of $I$. The players accept if and only if $c_{i}(g^{I}(x_{I},y_{I}))=1$.

Observe that $(f\circ g^{n})(x,y)=1$ if and only if the protocol has an
accepting computation on the inputs $x,y$. Observe further that the fact that
$\varphi$ is unambiguous implies that the protocol is unambiguous as well.
Finally, the number of bits communicated by the protocol is

$O(\log_{2}m+k\cdot\ell)\leq O\big{(}k\cdot\max(\log_{2}n,\ell)\big{)},$

completing the proof.

We turn to state a lower bound on the co-non-deterministic communication
complexity of composed functions $f\circ g^{n}$ for low-discrepancy functions
$g$. Its proof is given in Appendix A.

######  Theorem 3.2.

For every $\eta>0$ there exists $c>0$ for which the following holds. Let
$\ell$ and $n$ be integers such that $\ell\geq c\cdot\log_{2}n$, and let
$g:\\{0,1\\}^{\ell}\times\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}$ be a function
satisfying $\mathop{\mathrm{disc}}(g)\leq 2^{-\eta\cdot\ell}$. Then, for every
function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, it holds that

$\mathsf{coNP^{cc}}(f\circ
g^{n})\geq\Omega\big{(}\eta\cdot\mathsf{C}_{0}(f)\cdot\ell\big{)}.$

##  4 The Binary and Boolean Rank of Regular Matrices

In what follows we consider the notion of strongly unbiased functions and show
that compositions with such functions are associated with regular matrices. We
then present a strongly unbiased function and analyze its discrepancy.
Equipped with this function, we apply the lifting theorem from the previous
section to prove Theorem 1.1.

###  4.1 Strongly Unbiased Functions

Consider the following definition.

######  Definition 4.1.

Let $\ell$ be an integer. We call a function
$g:\\{0,1\\}^{\ell}\times\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}$ strongly
unbiased  if for every vector $x\in\\{0,1\\}^{\ell}$, the number of vectors
$y\in\\{0,1\\}^{\ell}$ satisfying $g(x,y)=1$ is $2^{\ell-1}$, and for every
vector $y\in\\{0,1\\}^{\ell}$, the number of vectors $x\in\\{0,1\\}^{\ell}$
satisfying $g(x,y)=1$ is $2^{\ell-1}$. Equivalently, $g$ is strongly unbiased
if the matrix associated with $g$ is $2^{\ell-1}$-regular.

The following lemma shows that compositions with strongly unbiased functions
are associated with regular matrices.

######  Lemma 4.2.

For all functions
$g:\\{0,1\\}^{\ell}\times\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}$ and
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, if $g$ is strongly unbiased then the
matrix associated with the composed function $f\circ g^{n}$ is regular.

  * Proof:

Let $g:\\{0,1\\}^{\ell}\times\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}$ be a
strongly unbiased function, let $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ be a
function, and let $M$ be the matrix of dimensions $2^{\ell\cdot n}\times
2^{\ell\cdot n}$ associated with the composed function $f\circ g^{n}$. Since
$g$ is strongly unbiased, it follows that for every vector
$x\in\\{0,1\\}^{\ell\cdot n}$ and for every vector $a\in\\{0,1\\}^{n}$,
precisely $2^{-n}$ fraction of the vectors $y\in\\{0,1\\}^{\ell\cdot n}$
satisfy $g^{n}(x,y)=a$. This implies that the row of the matrix $M$ that
corresponds to a vector $x\in\\{0,1\\}^{\ell\cdot n}$ consists of the
evaluations of the function $f$ on all vectors $a\in\\{0,1\\}^{n}$, where each
such evaluation appears exactly $2^{-n}\cdot 2^{\ell\cdot n}=2^{(\ell-1)n}$
times. In particular, the number of ones in this row is
$2^{(\ell-1)n}\cdot|f^{-1}(1)|$. Since this number is independent of $x$, it
follows that this is the number of ones in each row of the matrix $M$. By
symmetry, this is also the number of ones in each column of $M$, implying that
the matrix $M$ is regular.

###  4.2 The Gadget Function

For an integer $\ell\geq 1$, define the function
$g_{\ell}:\\{0,1\\}^{\ell}\times\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}$ by

$g_{\ell}(x,y)=x_{1}+y_{1}+\sum_{i=2}^{\ell}{x_{i}\cdot
y_{i}}~{}~{}(\mbox{mod}~{}2)$

for all $x,y\in\\{0,1\\}^{\ell}$. We first observe that $g_{\ell}$ is strongly
unbiased.

######  Lemma 4.3.

For every integer $\ell\geq 1$, the function $g_{\ell}$ is strongly unbiased.

  * Proof:

Consider the function $g_{\ell}$ for an integer $\ell\geq 1$. By definition,
for every $x\in\\{0,1\\}^{\ell}$, it holds that for every
$y^{\prime}\in\\{0,1\\}^{\ell-1}$ exactly one of the two vectors
$y\in\\{0,1\\}^{\ell}$ with suffix $y^{\prime}$ satisfies $g(x,y)=1$. This
implies that for every $x\in\\{0,1\\}^{\ell}$ precisely $2^{\ell-1}$ of the
vectors $y\in\\{0,1\\}^{\ell}$ satisfy $g(x,y)=1$. By symmetry, we also have
that for every $y\in\\{0,1\\}^{\ell}$ precisely $2^{\ell-1}$ of the vectors
$x\in\\{0,1\\}^{\ell}$ satisfy $g(x,y)=1$, so we are done.

We turn to show that the functions $g_{\ell}$ have low discrepancy. We note
that this can be directly derived from a bound on the discrepancy of the inner
product function. Yet, we present below a bound with a somewhat better
multiplicative constant, borrowing an argument of Bouda, Pivoluska, and Plesch
[4].

We start with some definitions. A Hadamard matrix is a $\pm 1$ matrix in which
every two distinct rows and every two distinct columns are orthogonal over the
reals. A standard example for a Hadamard matrix is the $2^{\ell}\times
2^{\ell}$ matrix $H_{\ell}$, with rows and columns indexed by the vectors of
$\\{0,1\\}^{\ell}$, defined by
$(H_{\ell})_{x,y}=(-1)^{\sum_{i=1}^{\ell}{x_{i}\cdot y_{i}}}$ for all
$x,y\in\\{0,1\\}^{\ell}$. A lemma of Lindsey asserts that every submatrix of a
Hadamard matrix is quite balanced (for a proof, see, e.g., [9, Lemma 8]).

######  Lemma 4.4 (Lindsey’s Lemma).

Let $H$ be an $n\times n$ Hadamard matrix. Then, the sum of elements in every
$r\times s$ submatrix of $H$ is at most $\sqrt{r\cdot s\cdot n}$.

######  Lemma 4.5.

For every integer $\ell\geq 1$, the discrepancy of the function $g_{\ell}$
satisfies $\mathop{\mathrm{disc}}(g_{\ell})\leq 2^{-(\ell+3)/2}$.

  * Proof:

Let $M$ denote the $2^{\ell}\times 2^{\ell}$ matrix associated with the
function $g_{\ell}$, and let $N$ be the $2^{\ell}\times 2^{\ell}$ matrix
defined by $N_{i,j}=(-1)^{M_{i,j}}$ for all $i,j\in[2^{\ell}]$. Observe that
the matrix $N$ is equal, up to a permutation of the rows and columns, to the
matrix

$\left(\begin{array}[]{cc}H&-H\\\ -H&H\\\ \end{array}\right),$

where $H=H_{\ell-1}$ is the $2^{\ell-1}\times 2^{\ell-1}$ matrix associated
with the inner product function on pairs of vectors of length $\ell-1$. Let
$A,B\subseteq[2^{\ell}]$ be sets of rows and columns in $N$, and consider the
combinatorial rectangle $R=A\times B$. We turn to show that the sum of
elements of $N$ in the entries of $R$ does not exceed $2^{3(\ell-1)/2}$.

Observe first that if the set $A$ includes both $i$ and $i+2^{\ell-1}$ for
some $i\in[2^{\ell-1}]$, then the sum of the elements of $N$ in the rows of
$A\times B$ that correspond to these indices is zero. Letting
$A^{\prime}\subseteq A$ be the set of rows obtained from $A$ by removing those
pairs, it suffices to bound the sum of elements of $N$ in the entries of
$A^{\prime}\times B$. Consider the $2^{\ell-1}\times 2^{\ell}$ submatrix
$N^{\prime}$ of $N$ defined as follows. For every $i\in[2^{\ell-1}]$, if $i\in
A^{\prime}$ then the $i$th row of $N^{\prime}$ is the $i$th row of $N$, and
otherwise it is the $i$th row of $N$ multiplied by $-1$ (i.e., the row of $N$
indexed by $i+2^{\ell-1}$). Observe that the rectangle $A^{\prime}\times B$ in
$N$ lies in the submatrix $N^{\prime}$ which can be written as
$N^{\prime}=(H^{\prime},-H^{\prime})$, where the $i$th row of $H^{\prime}$ is
either the $i$th row of $H$ or the $i$th row of $H$ multiplied by $-1$. Notice
that $H^{\prime}$ is a Hadamard matrix, and let $A^{\prime\prime}\times B$
denote the rectangle in $N^{\prime}$ that corresponds to the rectangle
$A^{\prime}\times B$ in $N$.

Next, observe that if the set $B$ includes both $i$ and $i+2^{\ell-1}$ for
some $i\in[2^{\ell-1}]$, then the sum of the elements of $N^{\prime}$ in the
columns of $A^{\prime\prime}\times B$ that correspond to these indices is
zero. As before, letting $B^{\prime}\subseteq B$ be the set of columns
obtained from $B$ by removing those pairs, it suffices to bound the sum of
elements of $N^{\prime}$ in the entries of $A^{\prime\prime}\times
B^{\prime}$. It now follows that this rectangle lies in a $2^{\ell-1}\times
2^{\ell-1}$ submatrix $H^{\prime\prime}$ of $N^{\prime}$, where the $i$th
column of $H^{\prime\prime}$ is either the $i$th column of $H^{\prime}$ or the
$i$th column of $H^{\prime}$ multiplied by $-1$. Notice that the matrix
$H^{\prime\prime}$ is a Hadamard matrix as well. By Lemma 4.4, the sum of
elements of $H^{\prime\prime}$ in the entries of $A^{\prime\prime}\times
B^{\prime}$ does not exceed $\sqrt{|A^{\prime\prime}|\cdot|B^{\prime}|\cdot
2^{\ell-1}}$. By $|A^{\prime\prime}|,|B^{\prime}|\leq 2^{\ell-1}$, it follows
that the latter is at most $2^{3(\ell-1)/2}$. As explained above, this is also
an upper bound on the sum of elements of $N$ in the entries of the rectangle
$R$.

Finally, let $m_{0}$ and $m_{1}$ denote, respectively, the numbers of zeros
and ones of $M$ in the entries of the rectangle $R$. It holds that
$|m_{0}-m_{1}|\leq 2^{3(\ell-1)/2}$, and this implies that

${\mathop{\mathrm{disc}}}_{R}(g_{\ell})=\Big{|}\frac{m_{0}-m_{1}}{2^{2\ell}}\Big{|}\leq\frac{2^{3(\ell-1)/2}}{2^{2\ell}}=2^{-(\ell+3)/2},$

completing the proof.

###  4.3 Proof of Theorem 1.1

We are ready to put everything together and to complete the proof of Theorem
1.1.

  * Proof of Theorem 1.1:

By Theorem 2.1, for infinitely many integers $r$, there exists a Boolean
function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ satisfying
$\mathsf{UC}_{1}(f)=r$ and $\mathsf{C}_{0}(f)\geq\widetilde{\Omega}(r^{2})$
where $r=n^{\Omega(1)}$. For an integer $\ell$, consider the function
$g_{\ell}:\\{0,1\\}^{\ell}\times\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}$ defined
in Section 4.2. By Lemma 4.5, it holds that
$\mathop{\mathrm{disc}}(g_{\ell})\leq 2^{-\eta\cdot\ell}$ for $\eta=1/2$.
Theorem 3.2 yields that there exists a constant $c$, such that for
$\ell=\lceil c\cdot\log_{2}n\rceil$, the composed function $f\circ
g_{\ell}^{n}$ satisfies

$\displaystyle\mathsf{coNP^{cc}}(f\circ
g_{\ell}^{n})\geq\Omega(\mathsf{C}_{0}(f)\cdot\ell)\geq\widetilde{\Omega}(r^{2}).$
(2)

By Lemma 3.1, it further holds that

$\mathsf{UP^{cc}}(f\circ g_{\ell}^{n})\leq
O(\mathsf{UC}_{1}(f)\cdot\ell)\leq\widetilde{O}(r),$ (3)

where for the second inequality we have used our choice of $\ell$ and the fact
that $r=n^{\Omega(1)}$.

To complete the proof, let $M$ be the square $2^{\ell\cdot n}\times
2^{\ell\cdot n}$ matrix associated with the composed function $f\circ
g_{\ell}^{n}$. By Lemma 4.3, the function $g_{\ell}$ is strongly unbiased,
hence by Lemma 4.2, the matrix $M$ is regular. Recalling that
$\mathsf{UP^{cc}}(f\circ
g_{\ell}^{n})=\lceil\log_{2}{\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)\rceil$,
it follows from (3) that

$\displaystyle{\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)\leq
2^{\widetilde{O}(r)}.$ (4)

Put $k={\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)$, and combine (2) and (4)
with the fact that $\mathsf{coNP^{cc}}(f\circ
g_{\ell}^{n})=\lceil\log_{2}{\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})\rceil$
to obtain that

${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})\geq
2^{\widetilde{\Omega}(r^{2})}\geq k^{\widetilde{\Omega}(\log k)},$

and we are done.

##  5 The Alon-Saks-Seymour Conjecture and Regular Graphs

In this section, we prove the following theorem.

######  Theorem 5.1.

For every square regular $0,1$ matrix $M$, there exists a simple regular graph
$G$ satisfying

${\mathop{\mathrm{bp}}}(G)\leq
33\cdot{\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)^{2}~{}~{}~{}\mbox{and}~{}~{}~{}\chi(G)\geq{\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})^{1/3}.$

As mentioned earlier, it was conjectured by Alon, Saks, and Seymour that every
graph $G$ satisfies $\mathop{\mathrm{bp}}(G)\geq\chi(G)-1$, and the conjecture
was disproved in a strong sense in a series of works. Applying Theorem 5.1 to
the matrices given by Theorem 1.1 yields regular graphs that form
counterexamples $G$ to the conjecture with a near optimal gap between
$\mathop{\mathrm{bp}}(G)$ and $\chi(G)$. This confirms Theorem 1.2.

###  5.1 Biclique Covering

We start with some definitions that will be used throughout the proof of
Theorem 5.1. All graphs considered here are undirected. They do not contain
parallel edges but they may have loops. As usual, a graph is said to be simple
if it contains no loops and no parallel edges. For a graph $G=(V,E)$, a
biclique of $G$ is a complete bipartite subgraph of $G$, that is, a pair
$(A,B)$ of sets $A,B\subseteq V$ where every vertex of $A$ is adjacent in $G$
to every vertex of $B$. For adjacent vertices $x,y$ of $G$ such that $x\in A$
and $y\in B$, we say that the biclique $(A,B)$ covers the oriented edge
$(x,y)$. Note that although the edges of $G$ are undirected, a biclique of $G$
covers edges of $G$ with some orientation. For a set $S\subseteq V$, we let
$G[S]$ denote the subgraph of $G$ induced by $S$.

For an integer $t$, a $t$-biclique covering of $G$ is a collection of
bicliques of $G$ that cover every edge of $G$ at least once and at most $t$
times. The minimum size of such a covering is called the $t$-biclique covering
number of $G$ and is denoted by ${\mathop{\mathrm{bp}}}_{t}(G)$. For $t=1$, a
$1$-biclique covering is also called a biclique partition, and we write
$\mathop{\mathrm{bp}}(G)=\mathop{\mathrm{bp}}_{1}(G)$.

We need the following result of Bousquet, Lagoutte, and Thomassé [6]. For the
sake of completeness, we include its short proof in Appendix B.

######  Claim 5.2 ([6, Claim 28]).

Let $H=(V,E)$ be a simple graph, and let ${\cal C}$ be a $t$-biclique covering
of size $k$ of $H$. Let $E^{\prime}\subseteq E$ be the set of edges of $H$
that are covered by ${\cal C}$ exactly $t$ times. Then, the graph
$H^{\prime}=(V,E^{\prime})$ satisfies
$\mathop{\mathrm{bp}}(H^{\prime})\leq(2k)^{t}$.

###  5.2 From Regular Matrices to Regular Graphs

We are ready to prove Theorem 5.1. Before its formal proof, let us briefly
describe the proof strategy. Given a regular $0,1$ matrix $M$, our goal is to
construct a simple regular graph $G$ such that its biclique partition number
is not much larger than the binary rank of $M$, and its chromatic number is
not much smaller than the Boolean rank of $M$. In the first phase of the
proof, we use $M$ to construct an intermediate graph $H$. While this graph is
not simple, it admits a $2$-biclique covering whose size equals the binary
rank of $M$, and it contains a simple subgraph whose chromatic number is at
least the Boolean rank of $M$. In the second phase of the proof, we use $H$ to
construct a simple regular graph $G$ with a relatively small $1$-biclique
covering and yet a large chromatic number. The regularity of the produced
graph $G$ crucially relies on the regularity of the matrix $M$.

  * Proof of Theorem 5.1:

Let $M$ be an $n\times n$ regular $0,1$ matrix, and let $d$ denote the number
of ones in each row and each column of $M$. Put
$k={\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)$ and
$m={\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})$.

We first define a graph $H=(V,E)$ on the vertex set $V=[n]\times[n]$ in which
every two (not necessarily distinct) vertices $(i_{1},j_{1}),(i_{2},j_{2})\in
V$ are adjacent if

$M_{i_{1},j_{2}}=1~{}~{}~{}\mbox{ or }~{}~{}~{}M_{i_{2},j_{1}}=1.$

Define $V_{0}=\\{(i,j)\in V~{}|~{}M_{i,j}=0\\}$ and $V_{1}=\\{(i,j)\in
V~{}|~{}M_{i,j}=1\\}$. Note that $V=V_{0}\cup V_{1}$, and notice that the
vertices of $H$ that have loops are precisely the vertices of $V_{1}$.

Let $H_{0}=H[V_{0}]$ denote the subgraph of $H$ induced on the vertices of
$V_{0}$. Clearly, $H_{0}$ is a simple graph. The following lemma relates its
chromatic number to the Boolean rank of $\overline{M}$.

######  Lemma 5.3.

The graph $H_{0}$ satisfies $\chi(H_{0})\geq m$.

    * Proof:

Put $r=\chi(H_{0})$. Then, there exists a partition of $V_{0}$ into $r$
independent sets $I_{1},\ldots,I_{r}$ of $H_{0}$. For each $t\in[r]$, let
$A_{t}$ be the set of elements $i\in[n]$ for which there exists some $j\in[n]$
such that $(i,j)\in I_{t}$, and let $B_{t}$ be the set of elements $j\in[n]$
for which there exists some $i\in[n]$ such that $(i,j)\in I_{t}$. Since
$I_{t}$ is an independent set in $H_{0}$, it follows that every pair $(i,j)\in
A_{t}\times B_{t}$ satisfies $M_{i,j}=0$. This implies that $A_{t}\times
B_{t}$ is a combinatorial rectangle of zeros in the matrix $M$. Since the $r$
given independent sets cover the entire set $V_{0}$, it follows that for every
pair $(i,j)\in V_{0}$ there exists some $t\in[r]$ such that $(i,j)\in I_{t}$,
and this $t$ satisfies $(i,j)\in A_{t}\times B_{t}$. This shows that the
rectangles $A_{t}\times B_{t}$ with $t\in[r]$ form a cover of the zeros of
$M$, hence $r\geq{\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})=m$, as
required.

The next lemma provides a $2$-biclique covering of $H$ whose size equals the
binary rank of $M$.

######  Lemma 5.4.

There exists a $2$-biclique covering ${\cal C}$ of $H$ such that

    1. 1.

$|{\cal C}|=k$,

    2. 2.

for every adjacent distinct vertices $(i_{1},j_{1}),(i_{2},j_{2})$ of $H$, if
both $M_{i_{1},j_{2}}=1$ and $M_{i_{2},j_{1}}=1$ hold, then the edge that
connects them is covered by ${\cal C}$ twice in the two opposite orientations,
and if only one of them holds, then it is covered by ${\cal C}$ once, and

    3. 3.

every loop of $H$ is covered by ${\cal C}$ once.

    * Proof:

By $k={\mathop{\mathrm{rank}}}_{\mathrm{bin}}(M)$, there exists a collection
of $k$ combinatorial rectangles $A_{t}\times B_{t}$ of ones, $t\in[k]$, that
forms a partition of the ones of the matrix $M$. For each $t\in[k]$, define

$C_{t}=(A_{t}\times[n],[n]\times B_{t}),$

and note that it follows from the definition of $H$ that $C_{t}$ is a
biclique. Let ${\cal C}$ be the collection of all the bicliques $C_{t}$ for
$t\in[k]$.

Let $(i_{1},j_{1}),(i_{2},j_{2})$ be two (not necessarily distinct) vertices
of $H$. If $M_{i_{1},j_{2}}=1$ then there exists a unique $t\in[k]$ such that
$(i_{1},j_{2})\in A_{t}\times B_{t}$. This implies that the oriented edge
$((i_{1},j_{1}),(i_{2},j_{2}))$ is covered by the biclique $C_{t}$ and is not
covered by any other biclique of ${\cal C}$. If, however, it holds that
$M_{i_{1},j_{2}}=0$, then no $t\in[k]$ satisfies $(i_{1},j_{2})\in A_{t}\times
B_{t}$, hence the oriented edge $((i_{1},j_{1}),(i_{2},j_{2}))$ is not covered
by any biclique of ${\cal C}$.

We turn to show that ${\cal C}$ is a $2$-biclique covering of $H$ that
satisfies the assertion of the lemma. By definition, we have $|{\cal C}|=k$,
as required for Item 1. Let $(i_{1},j_{1}),(i_{2},j_{2})$ be two distinct
vertices of $H$. If the vertices are adjacent then $M_{i_{1},j_{2}}=1$ or
$M_{i_{2},j_{1}}=1$. The above discussion implies that if both the conditions
hold then the edge that connects them is covered twice in the two opposite
orientations, whereas if only one of the conditions holds, then the edge is
covered once, as required for Item 2. For a vertex $(i,j)$ that has a loop, it
holds that $M_{i,j}=1$, hence the oriented edge $((i,j),(i,j))$ is covered
once by ${\cal C}$, as required for Item 3. On the other hand, if the vertices
$(i_{1},j_{1}),(i_{2},j_{2})$ are not adjacent then $M_{i_{1},j_{2}}=0$ and
$M_{i_{2},j_{1}}=0$, hence no oriented edge between them is covered by ${\cal
C}$. It thus follows that ${\cal C}$ is a $2$-biclique covering of $H$, and we
are done.

Let ${\cal C}$ be the $2$-biclique covering of $H$ given by Lemma 5.4.
Consider the two subgraphs of $H_{0}$ defined by $H_{0}^{(1)}=(V_{0},E_{1})$
and $H_{0}^{(2)}=(V_{0},E_{2})$, where $E_{t}$ is the set of edges of $H_{0}$
that are covered by ${\cal C}$ exactly $t$ times for $t\in[2]$. Notice that
the edge set of $H_{0}$ is $E_{1}\cup E_{2}$. By assigning to every vertex of
$H_{0}$ the pair of its colors according to some optimal proper colorings of
$H_{0}^{(1)}$ and $H_{0}^{(2)}$, it follows that

$\displaystyle\chi(H_{0})\leq\chi(H_{0}^{(1)})\cdot\chi(H_{0}^{(2)}).$ (5)

To obtain the desired simple regular graph, we proceed by considering the
following two cases according to the chromatic number of $H_{0}^{(2)}$.

#### Case 1.

Suppose first that $\chi(H_{0}^{(2)})\geq m^{1/3}$. Let ${\cal C}^{\prime}$ be
the collection of bicliques of $H$ obtained from ${\cal C}$ by replacing every
biclique $(A,B)\in{\cal C}$ by the three bicliques

$(A\cap B,A\cap B),~{}(A\cap B,B\setminus A),~{}\mbox{and}~{}(A\setminus
B,B),$

where bicliques with an empty part can be avoided. Observe that these three
bicliques cover precisely the same edges covered by $(A,B)$ with the same
multiplicities and orientations, where the first biclique has equal parts and
the other two have disjoint parts. Note that $A\cap B$ is not necessarily
empty because loops are allowed. It follows that ${\cal C}^{\prime}$ is a
$2$-biclique covering of $H$ of size $|{\cal C}^{\prime}|\leq 3k$ which
satisfies Items 2 and 3 of Lemma 5.4. Letting ${\cal
C}^{\prime\prime}\subseteq{\cal C}^{\prime}$ denote the collection of
bicliques of ${\cal C}^{\prime}$ with equal parts, it follows that $|{\cal
C}^{\prime\prime}|\leq k$ and $|{\cal C}^{\prime}\setminus{\cal
C}^{\prime\prime}|\leq 2k$.

Every biclique of ${\cal C}^{\prime\prime}$ has the form $(A,A)$ for some set
$A\subseteq V$. For every $x\in A$, it covers a loop of $x$ as an oriented
edge $(x,x)$, and for every distinct $x,y\in A$, it covers the edge that
connects $x$ and $y$ in the two opposite orientations, namely, as $(x,y)$ and
as $(y,x)$. This implies that all the vertices that appear in the bicliques of
${\cal C}^{\prime\prime}$ have loops in $H$ and thus belong to $V_{1}$. Since
the parts of the bicliques of ${\cal C}^{\prime}\setminus{\cal
C}^{\prime\prime}$ are disjoint, it follows that they do not cover any loops,
hence the bicliques of ${\cal C}^{\prime\prime}$ cover all the loops of $H$.
Since ${\cal C}^{\prime}$ is a $2$-biclique covering of $H$, it follows that
no edge is covered by both ${\cal C}^{\prime\prime}$ and ${\cal
C}^{\prime}\setminus{\cal C}^{\prime\prime}$.

Let $F$ be the graph obtained from $H$ by removing the edges of the bicliques
of ${\cal C}^{\prime\prime}$. Since the bicliques of ${\cal C}^{\prime\prime}$
cover all the loops of $H$, it follows that the graph $F$ is simple. The
collection ${\cal C}^{\prime}\setminus{\cal C}^{\prime\prime}$ forms a
$2$-biclique covering of $F$, hence ${\mathop{\mathrm{bp}}}_{2}(F)\leq 2k$.
Let $F^{(2)}$ denote the subgraph of $F$ on $V$ that includes all the edges
that are covered by ${\cal C}^{\prime}\setminus{\cal C}^{\prime\prime}$ twice.
Since the bicliques of ${\cal C}^{\prime\prime}$ involve only vertices of
$V_{1}$, it follows that $F^{(2)}$ has an induced subgraph isomorphic to
$H_{0}^{(2)}$, implying that

$\displaystyle\chi(F^{(2)})\geq\chi(H_{0}^{(2)})\geq m^{1/3}.$ (6)

Now, let $G$ be the graph that contains two disjoint copies of $F^{(2)}$, with
additional edges between the two copies according to the bicliques of ${\cal
C}^{\prime\prime}$. More precisely, $G$ is the graph on the vertex set
$V\times[2]$ in which two vertices $(x,b)$ and $(y,b)$ for $b\in[2]$ are
adjacent if $x$ and $y$ are adjacent in $F^{(2)}$, and two vertices $(x,1)$
and $(y,2)$ are adjacent if $(x,y)$ is an oriented edge covered by the
bicliques of ${\cal C}^{\prime\prime}$. The graph $G$ is simple, because
$F^{(2)}$ is simple and because no oriented edge is covered twice by ${\cal
C}^{\prime\prime}$. We claim that $G$ satisfies the assertion of the theorem.

Firstly, $G$ has an induced subgraph isomorphic to $F^{(2)}$, hence it follows
from (6) that

$\chi(G)\geq\chi(F^{(2)})\geq m^{1/3}.$

Secondly, we claim that $\mathop{\mathrm{bp}}(G)\leq 33\cdot k^{2}$. To see
this, use Claim 5.2 and ${\mathop{\mathrm{bp}}}_{2}(F)\leq 2k$ to obtain that
$\mathop{\mathrm{bp}}(F^{(2)})\leq(4k)^{2}$, that is, at most $(4k)^{2}$
bicliques are needed for a partition of the edges of each copy of $F^{(2)}$ in
$G$. Consider further the bicliques $(A\times\\{1\\},A\times\\{2\\})$ for
$(A,A)\in{\cal C}^{\prime\prime}$, which form a partition with size at most
$k$ of the edges of $G$ between the vertices of $V\times\\{1\\}$ and those of
$V\times\\{2\\}$. It follows that

$\mathop{\mathrm{bp}}(G)\leq 2\cdot(4k)^{2}+k\leq 33\cdot k^{2}.$

Finally, we claim that $G$ is regular with degree $d^{2}$. To see this,
consider an arbitrary vertex $(i_{1},j_{1},b)\in V\times[2]$ in $G$. This
vertex is adjacent to the vertices $(i_{2},j_{2},b)$ for which the pairs
$(i_{1},j_{1})$ and $(i_{2},j_{2})$ are adjacent in $H$ and the edge that
connects them is covered twice by ${\cal C}^{\prime}\setminus{\cal
C}^{\prime\prime}$. It is further adjacent to the vertices
$(i_{2},j_{2},b^{\prime})$ with $b^{\prime}\neq b$ for which the pairs
$(i_{1},j_{1})$ and $(i_{2},j_{2})$ are adjacent in $H$ and the edge that
connects them is covered by ${\cal C}^{\prime\prime}$ (twice if they are
distinct, and once otherwise). Since ${\cal C}^{\prime}$ satisfies Items 2 and
3 of Lemma 5.4, it follows that the degree of $(i_{1},j_{1},b)$ in $G$ is
precisely the number of pairs $(i_{2},j_{2})\in V$ satisfying
$M_{i_{1},j_{2}}=1$ and $M_{i_{2},j_{1}}=1$. By the $d$-regularity of $M$, the
latter is equal to $d^{2}$, so we are done.

#### Case 2.

Suppose next that $\chi(H_{0}^{(2)})<m^{1/3}$. We start by proving that there
exists an independent set $S\subseteq V_{0}$ in the graph $H_{0}^{(2)}$ for
which

$\chi(H_{0}^{(1)}[S])\geq m^{1/3}.$ (7)

Indeed, the assumption implies that there exists a proper coloring of
$H_{0}^{(2)}$ with fewer than $m^{1/3}$ colors. If the induced subgraph of
$H_{0}^{(1)}$ on every color class of this coloring has chromatic number
smaller than $m^{1/3}$, then one can obtain a proper coloring of $H_{0}^{(1)}$
whose number of colors is smaller than $m^{1/3}\cdot m^{1/3}=m^{2/3}$, which
implies using (5) that $\chi(H_{0})<m^{2/3}\cdot m^{1/3}=m$, in contradiction
to Lemma 5.3. This implies that some color class $S\subseteq V_{0}$ of the
coloring of $H_{0}^{(2)}$ satisfies (7).

Now, consider the $3$-partite graph $G^{\prime}$ whose vertex set consists of
three copies of $V$ that are connected by three copies of the bicliques of
${\cal C}$ oriented in a cyclic manner. More precisely, the vertex set of
$G^{\prime}$ is $V\times[3]$ and its edges are those of the bicliques

$(A\times\\{1\\},B\times\\{2\\}),~{}~{}(A\times\\{2\\},B\times\\{3\\}),~{}~{}\mbox{and}~{}~{}(A\times\\{3\\},B\times\\{1\\})$

for all $(A,B)\in{\cal C}$. By Lemma 5.4, no oriented edge of the bicliques of
${\cal C}$ is covered twice. It thus follows that $G^{\prime}$ is a simple
graph and that each of its edges is covered by the above bicliques exactly
once. By $|{\cal C}|=k$, it follows that $\mathop{\mathrm{bp}}(G^{\prime})\leq
3k$. Further, Items 2 and 3 of Lemma 5.4 imply that the degree of every vertex
$(i_{1},j_{1},b)\in V\times[3]$ of $G^{\prime}$ is precisely the sum of the
number of pairs $(i_{2},j_{2})\in V$ satisfying $M_{i_{1},j_{2}}=1$ and the
number of pairs $(i_{2},j_{2})\in V$ satisfying $M_{i_{2},j_{1}}=1$. Since the
matrix $M$ is $d$-regular, it follows that the graph $G^{\prime}$ is regular
with degree $2nd$.

We next define a graph $G$ as follows. The graph $G$ is obtained from
$G^{\prime}$ by removing all the edges whose both endpoints are in
$S\times[3]$ and by adding the edges of the induced subgraph $H[S]$ of $H$ on
$S$ to each of the three copies of $S$ in $G$ (i.e., $S\times\\{b\\}$ for
$b\in[3]$). Since $G^{\prime}$ is a simple graph, using the fact that $S$ is a
subset of $V_{0}$ and thus spans no loops, it follows that $G$ is a simple
graph as well. We claim that $G$ satisfies the assertion of the theorem.

Firstly, since $S$ is an independent set in $H_{0}^{(2)}$, the subgraph of $G$
induced on every copy of $S$ is isomorphic to $H_{0}^{(1)}[S]$. It thus
follows from (7) that

$\chi(G)\geq\chi(H_{0}^{(1)}[S])\geq m^{1/3}.$

Secondly, we claim that $\mathop{\mathrm{bp}}(G)\leq 9k$. To see this, recall
that $\mathop{\mathrm{bp}}(G^{\prime})\leq 3k$, and consider some biclique
partition with size at most $3k$ of the edges of $G^{\prime}$. Replace each
biclique $(A\times\\{b\\},B\times\\{b^{\prime}\\})$ of this partition, where
$b\neq b^{\prime}$, by the two bicliques

$((A\setminus S)\times\\{b\\},B\times\\{b^{\prime}\\})~{}\mbox{ and
}~{}((A\cap S)\times\\{b\\},(B\setminus S)\times\\{b^{\prime}\\}).$

This gives us a biclique partition with size at most $6k$ of all the edges of
$G^{\prime}$ but those spanned by the vertices of $S\times[3]$. It remains to
cover the edges of the three copies of $H[S]$ in $G$. Since $S$ is an
independent set in $H_{0}^{(2)}$, each edge of $H[S]$ is covered by ${\cal C}$
exactly once, so by restricting the bicliques of ${\cal C}$ to the vertices of
$S$, we get a biclique partition of $H[S]$ with size at most $k$. This gives
us a biclique partition with size at most $k$ of the edges of
$G[V\times\\{b\\}]$ for each $b\in[3]$, implying that
$\mathop{\mathrm{bp}}(G)\leq 6k+3k=9k$.

Finally, we claim that $G$ is regular. To see this, recall that $G^{\prime}$
is regular and that $G$ is obtained from $G^{\prime}$ by replacing the edges
between the different copies of $S$ by the corresponding edges inside the
copies of $S$. Since those edges are covered exactly once by ${\cal C}$, this
does not change the degrees of the vertices, yielding that the graph $G$ is
regular as well, and we are done.

## Acknowledgements

We thank the anonymous reviewers for their helpful and constructive comments.

## References

  * [1] K. Amano.  Some improved bounds on communication complexity via new decomposition of cliques.  Discret. Appl. Math., 166:249–254, 2014.
  * [2] K. Balodis, S. Ben-David, M. Göös, S. Jain, and R. Kothari.  Unambiguous DNFs and Alon-Saks-Seymour.  In IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS’21), pages 116–124. IEEE, 2021.
  * [3] S. Ben-David, P. Hatami, and A. Tal.  Low-sensitivity functions from unambiguous certificates.  In 8th Innovations in Theoretical Computer Science Conference (ITCS’17), pages 28:1–28:23, 2017.
  * [4] J. Bouda, M. Pivoluska, and M. Plesch.  Improving the Hadamard extractor.  Theor. Comput. Sci., 459:69–76, 2012.
  * [5] N. Bousquet, A. Lagoutte, F. Maffray, and L. Pastor.  Decomposition techniques applied to the clique-stable set separation problem.  Discret. Math., 341(5):1492–1501, 2018.
  * [6] N. Bousquet, A. Lagoutte, and S. Thomassé.  Clique versus independent set.  European J. Combinatorics, 40:73–92, 2014.
  * [7] R. A. Brualdi, R. Manber, and J. A. Ross.  On the minimum rank of regular classes of matrices of zeros and ones.  J. Combin. Theory Ser. A, 41(1):32–49, 1986.
  * [8] A. Chattopadhyay, Y. Filmus, S. Koroth, O. Meir, and T. Pitassi.  Query-to-communication lifting using low-discrepancy gadgets.  SIAM J. Comput., 50(1):171–210, 2021.  Preliminary version in ICALP’19.
  * [9] B. Chor and O. Goldreich.  Unbiased bits from sources of weak randomness and probabilistic communication complexity.  SIAM J. Comput., 17(2):230–261, 1988.  Preliminary version in FOCS’85.
  * [10] M. Chudnovsky and P. Seymour.  Subdivided claws and the clique-stable set separation property.  In 2019–20 MATRIX Annals, volume 4, pages 483–487. Springer, 2021\.
  * [11] S. M. Cioabă and M. Tait.  More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures.  Electron. J. Combinatorics, 18(1), 2011.
  * [12] D. de Caen, D. A. Gregory, and N. J. Pullman.  The Boolean rank of zero-one matrices.  Proc. of the 3rd Caribbean Conference on Combinatorics and Computing, pages 169–173, 1981.
  * [13] M. Göös.  Lower bounds for clique vs. independent set.  In IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS’15), pages 1066–1076, 2015.
  * [14] M. Göös, S. Lovett, R. Meka, T. Watson, and D. Zuckerman.  Rectangles are nonnegative juntas.  SIAM J. Comput., 45(5):1835–1869, 2016.  Preliminary version in STOC’15.
  * [15] M. Göös, T. Pitassi, and T. Watson.  Deterministic communication vs. partition number.  SIAM J. Comput., 47(6):2435–2450, 2018.  Preliminary version in FOCS’15.
  * [16] R. L. Graham and H. O. Pollak.  On the addressing problem for loop switching.  Bell Syst. Tech. J., 50(8):2495–2519, 1971.
  * [17] D. A. Gregory, N. J. Pullman, K. F. Jones, and J. R. Lundgren.  Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices.  J. Comb. Theory, Ser. B, 51(1):73–89, 1991.
  * [18] K. A. S. Hefner, T. D. Henson, J. R. Lundgren, and J. S. Maybee.  Biclique coverings of bigraphs and digraphs and minimum semiring ranks of $\\{0,1\\}$-matrices.  Congr. Numer., 71:115–122, 1990.
  * [19] H. Huang and B. Sudakov.  A counterexample to the Alon-Saks-Seymour conjecture and related problems.  Combinatorica, 32(2):205–219, 2012.
  * [20] S. Jukna.  Boolean Function Complexity – Advances and Frontiers, volume 27 of Algorithms and Combinatorics.  Springer, 2012.
  * [21] J. Kahn.  Recent results on some not-so-recent hypergraph matching and covering problems.  In Extremal Problems for Finite Sets, pages 305–353. Bolyai Soc. Math. Stud., 1994.
  * [22] P. K. Kothari, R. Meka, and P. Raghavendra.  Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs.  In Proc. of the 49th Annual ACM Symposium on Theory of Computing (STOC’17), pages 590–603, 2017.
  * [23] A. Lagoutte and T. Trunck.  Clique-stable set separation in perfect graphs with no balanced skew-partitions.  Discret. Math., 339(6):1809–1825, 2016.
  * [24] L. Lovász and M. E. Saks.  Lattices, Möbius functions and communication complexity.  In IEEE 29th Annual Symposium on Foundations of Computer Science (FOCS’88), pages 81–90, 1988.
  * [25] S. Lovett.  Recent advances on the log-rank conjecture in communication complexity.  Bull. EATCS, 112, 2014.
  * [26] S. D. Monson, N. J. Pullman, and R. Rees.  A survey of clique and biclique coverings and factorizations of $(0,1)$-matrices.  Bull. Inst. Combin. Appl., 14:17–86, 1995.
  * [27] N. J. Pullman.  Ranks of binary matrices with constant line sums.  Linear Algebra Appl., 104:193–197, 1988.
  * [28] A. A. Razborov.  The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear.  Discret. Math., 108(1–3):393–396, 1992.
  * [29] M. Shigeta and K. Amano.  Ordered biclique partitions and communication complexity problems.  Discret. Appl. Math., 184:248–252, 2015.
  * [30] M. Yannakakis.  Expressing combinatorial optimization problems by linear programs.  J. Comput. Syst. Sci., 43(3):441–466, 1991.  Preliminary version in STOC’88.
  * [31] A. C. Yao.  Some complexity questions related to distributive computing.  In Proc. of the 11th Annual ACM Symposium on Theory of Computing (STOC’79), pages 209–213, 1979.

## Appendix

##  Appendix A Proof of Theorem 3.2

In this appendix we prove Theorem 3.2. We need the following definitions.

######  Definition A.1 (Min-entropy).

The min-entropy $\mbox{H}_{\infty}(X)$ of a discrete random variable $X$ is
defined as

$\mbox{H}_{\infty}(X)=\min_{x\in\mathop{\mathrm{supp}}(X)}{\log_{2}\frac{1}{{\Pr\left[{X=x}\right]}}}.$

Equivalently, $\mbox{H}_{\infty}(X)$ is the smallest $b$ for which
${\Pr\left[{X=x}\right]}\leq 2^{-b}$ for every $x$ in the support of $X$.

######  Definition A.2 (Density).

A pair $(X,Y)$ of random variables over $\\{0,1\\}^{\ell\cdot n}$ is called
$\delta$-dense if for all sets $I\subseteq[n]$, it holds that
$\mbox{H}_{\infty}(X_{I},Y_{I})\geq\delta\cdot 2\ell|I|$.

We further need the following proposition that was proved in [8]. It says,
roughly speaking, that if
$g:\\{0,1\\}^{\ell}\times\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}$ is a function
with low discrepancy and $(X,Y)$ is a pair of independent random variables
over $\\{0,1\\}^{\ell\cdot n}$ whose projection to the blocks of a set
$S\subseteq[n]$ is sufficiently dense, then the distribution of
$g^{S}(X_{S},Y_{S})$ is close to uniform. A special case of this statement,
for $g$ being the inner product function, was previously given in [14, Lemma
13] (see also [13, Lemma 9]).

######  Proposition A.3 ([8, Proposition 3.10]).

There exists an absolute constant $h$, such that for every $\eta>0$ there
exists $c>0$ for which the following holds. Let $\ell$ and $n$ be integers
such that $\ell\geq c\cdot\log_{2}n$, and let
$g:\\{0,1\\}^{\ell}\times\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}$ be a function
satisfying $\mathop{\mathrm{disc}}(g)\leq 2^{-\eta\cdot\ell}$. For any
$\gamma>0$, let $S\subseteq[n]$ be a set, and let $X$ and $Y$ be independent
random variables over $\\{0,1\\}^{\ell\cdot n}$, such that $(X_{S},Y_{S})$ is
$\delta$-dense for $\delta\geq 1+\frac{1}{2}(\gamma-\eta+h/c)$. Then, for
every $a\in\\{0,1\\}^{|S|}$, it holds that

$\Big{|}{\Pr\left[{g^{S}(X_{S},Y_{S})=a}\right]}-2^{-|S|}\Big{|}\leq
2^{-|S|}\cdot 2^{-\gamma\cdot\ell}.$

Equipped with Proposition A.3, we are ready to prove Theorem 3.2.

  * Proof of Theorem 3.2:

Fix $\eta>0$. For some $c>0$ to be determined later, let $\ell$ and $n$ be two
integers such that $\ell\geq c\cdot\log_{2}n$, and let
$g:\\{0,1\\}^{\ell}\times\\{0,1\\}^{\ell}\rightarrow\\{0,1\\}$ be a function
satisfying $\mathop{\mathrm{disc}}(g)\leq 2^{-\eta\cdot\ell}$. We may and will
assume that $n\geq 2$. For a function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$,
put $t=\mathsf{coNP^{cc}}(f\circ g^{n})$, and let $M$ denote the $2^{\ell\cdot
n}\times 2^{\ell\cdot n}$ matrix associated with $f\circ g^{n}$. It follows
that ${\mathop{\mathrm{rank}}}_{\mathbb{B}}(\overline{M})\leq 2^{t}$, hence
there exists a cover $\Pi$ of the zeros of $M$ with at most $2^{t}$
monochromatic combinatorial rectangles.

Our goal is to show that for some $k\leq O(\frac{t}{\eta\cdot\ell})$ it holds
that $\mathsf{C}_{0}(f)\leq k$, that is, the function $\neg f$ can be
represented as a $k$-DNF formula. To do so, it suffices to show that for every
$z\in\\{0,1\\}^{n}$ satisfying $f(z)=0$, there exists a set $I\subseteq[n]$ of
size $|I|\leq k$ such that all vectors $z^{\prime}\in\\{0,1\\}^{n}$ with
$z^{\prime}_{I}=z_{I}$ are mapped by $f$ to $0$. Indeed, for every such $z$
and $I$, one can define a conjunction with $|I|$ literals which forms an
indicator for the vectors that agree with $z$ on the variables of $I$. The
disjunction of all of these conjunctions is an $n$-variate $k$-DNF formula
that precisely computes $\neg f$, as required.

Fix a vector $z\in\\{0,1\\}^{n}$ satisfying $f(z)=0$. Let $(X,Y)$ be the
random variable uniformly distributed over the set

$(g^{n})^{-1}(z)=\Big{\\{}(x,y)\in\\{0,1\\}^{\ell\cdot
n}\times\\{0,1\\}^{\ell\cdot n}\Bigm{|}g^{n}(x,y)=z\Big{\\}}.$

Observe that the random variables $(X_{i},Y_{i})$ for $i\in[n]$ are
independent and that each of them is uniformly distributed over either
$g^{(-1)}(0)$ or $g^{(-1)}(1)$. The assumption $\mathop{\mathrm{disc}}(g)\leq
2^{-\eta\cdot\ell}$ implies that the discrepancy of $g$ on the rectangle
$\\{0,1\\}^{\ell}\times\\{0,1\\}^{\ell}$ does not exceed $2^{-\eta\cdot\ell}$,
hence

$\big{|}|g^{-1}(0)|-|g^{-1}(1)|\big{|}\leq 2^{(2-\eta)\cdot\ell}.$

This implies that

$\min\big{(}|g^{-1}(0)|,|g^{-1}(1)|\big{)}\geq
2^{2\ell-1}-2^{(2-\eta)\cdot\ell-1}\geq 2^{2\ell-2},$

where the second inequality holds for $\ell\geq c\cdot\log_{2}n$ assuming that
$c\geq 1/\eta$. It thus follows that for every set $I\subseteq[n]$, it holds
that

$\displaystyle\mbox{H}_{\infty}(X_{I},Y_{I})=\sum_{i\in
I}{\mbox{H}_{\infty}(X_{i},Y_{i})}\geq|I|\cdot\log_{2}(2^{2\ell-2})=|I|\cdot(2\ell-2).$
(8)

By $f(z)=0$, the entries of $(g^{n})^{-1}(z)$ in $M$ are all zeros. Since
$\Pi$ is a cover of the zeros in $M$ with at most $2^{t}$ rectangles, there
must exist a rectangle $R\in\Pi$ that covers at least $2^{-t}$ fraction of the
entries of $(g^{n})^{-1}(z)$. Let $(X^{\prime},Y^{\prime})$ be the random
variable uniformly distributed over $(g^{n})^{-1}(z)\cap R$. Note that for
every $I\subseteq[n]$, the random variable $(X^{\prime}_{I},Y^{\prime}_{I})$
is obtained from $(X_{I},Y_{I})$ by conditioning it on the event $(X,Y)\in R$,
whose probability is at least $2^{-t}$. It thus follows, using (8), that for
every $I\subseteq[n]$,

$\displaystyle\mbox{H}_{\infty}(X^{\prime}_{I},Y^{\prime}_{I})\geq\mbox{H}_{\infty}(X_{I},Y_{I})-t\geq|I|\cdot(2\ell-2)-t.$
(9)

The following lemma shows that by fixing relatively few blocks in
$(X^{\prime},Y^{\prime})$, one can get a random variable that is quite dense
on the remaining blocks (recall Definition A.2).

######  Lemma A.4.

For every $\delta<1-\frac{1}{\ell}$, there exist a set $I\subseteq[n]$ of size
$|I|\leq\frac{t}{2\cdot((1-\delta)\ell-1)}$ and an assignment
$\alpha\in\\{0,1\\}^{2\cdot\ell|I|}$ for which the random variable
$(X^{\prime\prime},Y^{\prime\prime})$ obtained from $(X^{\prime},Y^{\prime})$
by conditioning it on the event $(X^{\prime}_{I},Y^{\prime}_{I})=\alpha$
satisfies that its projection
$(X^{\prime\prime}_{\overline{I}},Y^{\prime\prime}_{\overline{I}})$ to the
blocks of $\overline{I}=[n]\setminus I$ is $\delta$-dense. In addition,
letting $X^{\prime\prime\prime}$ and $Y^{\prime\prime\prime}$ be independent
copies of $X^{\prime\prime}$ and $Y^{\prime\prime}$ respectively, the random
variable
$(X^{\prime\prime\prime}_{\overline{I}},Y^{\prime\prime\prime}_{\overline{I}})$
is $(2\delta-1)$-dense.

    * Proof:

Fix an arbitrary $\delta<1-\frac{1}{\ell}$. If the random variable
$(X^{\prime},Y^{\prime})$ is $\delta$-dense, then the choice $I=\emptyset$
clearly satisfies the assertion of the first part of the lemma. Otherwise,
$(X^{\prime},Y^{\prime})$ is not $\delta$-dense, so there exists a set
$I\subseteq[n]$ for which
$\mbox{H}_{\infty}(X^{\prime}_{I},Y^{\prime}_{I})<\delta\cdot 2\ell|I|$. Let
$I$ be such a set with maximum size. By (9), we obtain that

$|I|\cdot(2\ell-2)-t\leq\mbox{H}_{\infty}(X^{\prime}_{I},Y^{\prime}_{I})<\delta\cdot
2\ell|I|,$

which implies, using $\delta<1-\frac{1}{\ell}$, that
$|I|\leq\frac{t}{2\cdot((1-\delta)\ell-1)}$.

It follows from $\mbox{H}_{\infty}(X^{\prime}_{I},Y^{\prime}_{I})<\delta\cdot
2\ell|I|$ that there exists an $\alpha\in\\{0,1\\}^{2\cdot\ell|I|}$ for which
the probability that $(X^{\prime}_{I},Y^{\prime}_{I})=\alpha$ is larger than
$2^{-\delta\cdot 2\ell|I|}$. Let $(X^{\prime\prime},Y^{\prime\prime})$ be the
random variable obtained from $(X^{\prime},Y^{\prime})$ by conditioning it on
the event $(X^{\prime}_{I},Y^{\prime}_{I})=\alpha$. We claim that its
projection $(X^{\prime\prime}_{\overline{I}},Y^{\prime\prime}_{\overline{I}})$
to the blocks of $\overline{I}$ is $\delta$-dense. To see this, suppose in
contradiction that there exists a non-empty set $J\subseteq\overline{I}$ and
an assignment $\beta\in\\{0,1\\}^{2\cdot\ell|J|}$ for which the probability
that $(X^{\prime\prime}_{J},Y^{\prime\prime}_{J})=\beta$ is larger than
$2^{-\delta\cdot 2\ell|J|}$. It thus follows that the probability that
$(X^{\prime}_{I},Y^{\prime}_{I})=\alpha$ and
$(X^{\prime}_{J},Y^{\prime}_{J})=\beta$ is larger than $2^{-\delta\cdot
2\ell|I|}\cdot 2^{-\delta\cdot 2\ell|J|}=2^{-\delta\cdot 2\ell|I\cup J|}$,
hence the set $I\cup J$ violates the $\delta$-density of
$(X^{\prime},Y^{\prime})$ and contradicts the maximality of $I$.

Now, let $X^{\prime\prime\prime}$ and $Y^{\prime\prime\prime}$ be independent
copies of $X^{\prime\prime}$ and $Y^{\prime\prime}$ respectively. We turn to
show that the random variable
$(X^{\prime\prime\prime}_{\overline{I}},Y^{\prime\prime\prime}_{\overline{I}})$
is $(2\delta-1)$-dense. To see this, fix any $J\subseteq\overline{I}$, and
observe that

$\mbox{H}_{\infty}(X^{\prime\prime\prime}_{J})\geq\mbox{H}_{\infty}(X^{\prime\prime}_{J},Y^{\prime\prime}_{J})-\mbox{H}_{\infty}(Y^{\prime\prime}_{J})\geq\delta\cdot
2\ell|J|-\ell|J|=(2\delta-1)\cdot\ell|J|.$

Similarly, we have
$\mbox{H}_{\infty}(Y^{\prime\prime\prime}_{J})\geq(2\delta-1)\cdot\ell|J|$. We
derive that

$\mbox{H}_{\infty}(X^{\prime\prime\prime}_{J},Y^{\prime\prime\prime}_{J})=\mbox{H}_{\infty}(X^{\prime\prime\prime}_{J})+\mbox{H}_{\infty}(Y^{\prime\prime\prime}_{J})\geq(2\delta-1)\cdot
2\ell|J|,$

which implies that
$(X^{\prime\prime\prime}_{\overline{I}},Y^{\prime\prime\prime}_{\overline{I}})$
is $(2\delta-1)$-dense, as desired.

We turn to apply Proposition A.3. Put $\gamma=1/\ell$. For the given $\eta>0$,
define

$\delta=1+\frac{1}{4}\cdot\Big{(}\gamma-\eta+\frac{h}{c}\Big{)},$

where $h$ is the constant given in the proposition. The assumption $\ell\geq
c\cdot\log_{2}n\geq c$ implies, for a sufficiently large $c$, say
$c>\max\big{(}2\cdot(h+1),9\big{)}\cdot\eta^{-1}$, that

$\displaystyle\delta\leq
1+\frac{1}{4}\cdot\Big{(}-\eta+\frac{h+1}{c}\Big{)}<1-\frac{\eta}{8}<1-\frac{1}{c}\leq
1-\frac{1}{\ell}.$ (10)

By (10), we can apply Lemma A.4 with the above $\delta$. Let $I\subseteq[n]$
and $\alpha\in\\{0,1\\}^{2\cdot\ell|I|}$ be the set and assignment given by
the lemma for this $\delta$, and let $(X^{\prime\prime},Y^{\prime\prime})$ and
$(X^{\prime\prime\prime},Y^{\prime\prime\prime})$ be the corresponding random
variables. Using the inequality $\delta<1-\frac{\eta}{8}$ that follows from
(10), we obtain from Lemma A.4 that $|I|\leq O(\frac{t}{\eta\cdot\ell})$ and
that the random variable
$(X^{\prime\prime\prime}_{\overline{I}},Y^{\prime\prime\prime}_{\overline{I}})$
is $(2\delta-1)$-dense. Notice that

$2\delta-1=1+\frac{1}{2}\cdot\Big{(}\gamma-\eta+\frac{h}{c}\Big{)}.$

This allows us to apply Proposition A.3 with the set $S=\overline{I}$ and to
obtain, assuming that $c=c(\eta)$ is sufficiently large, that for every
$a\in\\{0,1\\}^{|S|}$,

$\Big{|}{\Pr\left[{g^{S}(X^{\prime\prime\prime}_{S},Y^{\prime\prime\prime}_{S})=a}\right]}-2^{-|S|}\Big{|}\leq
2^{-(|S|+1)}.$

This in particular yields that the random variable
$g^{n}(X^{\prime\prime\prime},Y^{\prime\prime\prime})$ has full support on the
entries of $\overline{I}$.

It remains to show that for every $z^{\prime}\in\\{0,1\\}^{n}$ that satisfies
$z^{\prime}_{I}=z_{I}$, it holds that $f(z^{\prime})=0$. Let $R^{\prime}$ be
the rectangle of the matrix $M$ whose rows and columns are the supports of
$X^{\prime\prime\prime}$ and $Y^{\prime\prime\prime}$ respectively. Since the
rows and columns of $R^{\prime}$ are also rows and columns of $R$, it follows
that $R^{\prime}\subseteq R$, hence all of its pairs are mapped by $f\circ
g^{n}$ to zero. By construction, the pairs $(x,y)\in R^{\prime}$ satisfy
$(x_{I},y_{I})=\alpha$, and it holds that $z\in g^{n}(R^{\prime})$. Since the
random variable $g^{n}(X^{\prime\prime\prime},Y^{\prime\prime\prime})$ has
full support on the entries of $\overline{I}$, it follows that for every
vector $z^{\prime}\in\\{0,1\\}^{n}$ with $z^{\prime}_{I}=z_{I}$, there exists
a pair $(x,y)\in R^{\prime}$ such that $g^{n}(x,y)=z^{\prime}$. Since the
pairs of $R^{\prime}$ are mapped by $f\circ g^{n}$ to zero, we get that
$(f\circ g^{n})(x,y)=f(g^{n}(x,y))=f(z^{\prime})=0$, and we are done.

##  Appendix B Proof of Claim 5.2

  * Proof of Claim 5.2:

Let $(A_{1},B_{1}),\ldots,(A_{k},B_{k})$ be the $k$ bicliques of the
$t$-biclique covering ${\cal C}$ of $H$. By definition, every edge of
$E^{\prime}$ is covered by exactly $t$ of the bicliques of ${\cal C}$.
Consider the function that maps every such edge $e=\\{u,v\\}\in E^{\prime}$ to
a label $L=(i_{1},\ldots,i_{t},P)$, where $i_{1}<\cdots<i_{t}$ are the $t$
indices $i\in[k]$ for which the biclique $(A_{i},B_{i})$ covers the edge $e$,
and $P=\\{P_{1},P_{2}\\}$ is a partition of $[t]$ defined by
$P_{1}=\\{j\in[t]\mid u\in A_{i_{j}}\\}$ and $P_{2}=\\{j\in[t]\mid u\in
B_{i_{j}}\\}$. Note that the partition $P$ can be equivalently defined using
the vertex $v$ rather than $u$.

We claim that for every label $L$, the edges of $E^{\prime}$ that are mapped
to $L$ form a biclique in $H^{\prime}$, and that these bicliques are edge-
disjoint. To see this, suppose that two edges
$\\{u,v\\},\\{u^{\prime},v^{\prime}\\}\in E^{\prime}$ are mapped to the same
label $L=(i_{1},\ldots,i_{t},P)$. Then, the two edges are covered by all the
bicliques $(A_{i_{j}},B_{i_{j}})$ with $j\in[t]$, and it can be assumed,
without loss of generality, that $u$ and $u^{\prime}$ belong to the same part
in each of them. This implies that these bicliques also cover the edges
$\\{u,v^{\prime}\\}$ and $\\{u^{\prime},v\\}$. Since ${\cal C}$ is a
$t$-biclique covering of $H$, it follows that these edges belong to
$E^{\prime}$ and are also mapped to the label $L$. This implies that the edges
of $E^{\prime}$ that are mapped to $L$ form a biclique in $H^{\prime}$. Since
the label of every edge in $E^{\prime}$ is uniquely defined, every such edge
is covered by exactly one of these bicliques. It thus follows that the
collection of bicliques associated with all possible labels forms a biclique
partition of $H^{\prime}$. Since the number of labels is at most $(2k)^{t}$,
it follows that $\mathop{\mathrm{bp}}(H^{\prime})\leq(2k)^{t}$, as desired.