<p>(I tried to post this as a comment to Stasys' answer above, but this text is too long for a comment, so posting it as an answer.) Ivan Mihajlin (@ivmihajlin) came up with the following construction. Similarly to Stasys' proof, it works for the case when the maximum (rather than average) number of 0’s in each row is bounded.</p>

<p>First, consider the case when every row contains exactly two zeros. Consider the following undirected graph: the set of vertices is $[n]$; two nodes $i$ and $j$ are joined by an edge, if there is a row having zeros in columns $i$ and $j$. The graph has $n$ edges and hence it contains a cut $(L,R)$ of size at least $n/2$. This cut splits the columns of the matrix into two parts ($L$ and $R$). Let now also split the rows into two parts: the top part $T$ contains all columns that have exactly one zero in both $L$ and $R$; the bottom part $B$ contains all the remaining rows. What is nice about the top part of the matrix ($T \times (L \cup R)$) is that it can be computed by $O(n)$ gates. For the bottom part, let’s cut all-1 columns out of it and make a recursive call. The corresponding recurrence relation is $C(n) \le an + C(n/2)$ implying $C(n)=O(n)$.</p>

<p>Now, generalize it to the case of at most $d$ zeros in every row. Let $C_d(n)$ be the complexity of an $n \times (\le dn)$ matrix with at most $d$ zeros per row (if there are more than $dn$ columns, then some of them are all-1). Partition the columns into two parts $L$ and $R$ such that at least $n(1-2^{-d})$ rows (call them $T$) satisfy the following property: if there are exactly $d$ zeroes in a row, then not all of them belong to the same part (denote the remaining rows by $B$). Then make three recursive calls: $T \times L$, $T \times R$, and $B \times (L \cup R)$. This gives a recurrence relation $C_d(n) \le an + 2\cdot C_{d-1}(n(1-2^{-d}))+C_d(2^{-d}n)$. This, in turn, implies that $C_d(n) \le f(d)\cdot n$. The function $f(d)$ is exponential, but still.  </p>

CC BY-SA 3.0
2018-01-03T20:19:18.133Z
A nice argument. But it seems to be tailor made for the case of d=2 zeros per row. What about d>2 zeros?
Stasys
CC BY-SA 3.0
2018-01-04T10:12:16.897Z
@Stasys, it is doable if I'm not mistaken. I've updated the answer.
Alexander S. Kulikov
CC BY-SA 3.0
2018-01-03T10:13:17.520Z
2018-01-04T10:11:45.933Z
2018-01-04T10:11:45.933Z
Alexander S. Kulikov
<p>This is a partial (affirmative) answer in the case when we have an upper bound on the number of zeros in every row or in every column.</p>
<p>
A <i>rectangle</i> is a boolean matrix consisting of one all-1 submatrix and having zeros elsewhere. 
An OR-rank <span class="math-container">$rk(A)$</span> of a boolean matrix is the smallest number <span class="math-container">$r$</span> of
rectangles such that <span class="math-container">$A$</span> can be written as a (componentwise) OR of these rectangles. That is, every 1-entry of <span class="math-container">$A$</span> is a 1-entry in at least one of the rectangles, and every 0-entry of <span class="math-container">$A$</span> is a 0-entry in all rectangles. Note that <span class="math-container">$\log rk(A)$</span> is exactly the nondeterministic communication complexity of the matrix <span class="math-container">$A$</span> (where Alice gets rows, and Bob columns).
 As OP wrote, every boolean <span class="math-container">$m\times n$</span> matrix <span class="math-container">$A=(a_{i,j})$</span> defines a mapping <span class="math-container">$y=Ax$</span>, where  <span class="math-container">$y_i=\bigvee_{j=1}^na_{i,j}x_j$</span> for <span class="math-container">$i=1,\ldots,m$</span>. That is, we take a matrix-vector product over the boolean semiring.
<p>
<p>The following lemma is due to Pudlák and Rödl; see Proposition 10.1 in <a href="http://www.sciencedirect.com/science/article/pii/0012365X9400115Y" rel="nofollow noreferrer">this paper</a>
or Lemma 2.5 in <a href="https://web.vu.lt/mif/s.jukna//Knizka/" rel="nofollow noreferrer">this book</a> for a direct construction.</p>
<blockquote>
<b>Lemma 1:</b> For every boolean <span class="math-container">$n\times n$</span> matrix <span class="math-container">$A$</span>, the mapping <span class="math-container">$y=Ax$</span> can be computed by an unbounded fanin OR-circuit of depth-3 using at most <span class="math-container">$O(rk(A)\cdot n/\log n)$</span> wires.
</blockquote>
<p>We also have the following upper bound on the OR-rank of dense matrices.
The argument is a simple variation of that used by Alon in <a href="http://www.math.tau.ac.il/%7Enogaa/PDFS/Publications/Covering%20graphs%20by%20the%20minimum%20number%20of%20equivalence%20relations.pdf" rel="nofollow noreferrer">this paper</a>.</p>
<blockquote>
<b>Lemma 2:</b> If every column or every row of a boolean matrix <span class="math-container">$A$</span> contains at most <span class="math-container">$d$</span> zeros, then <span class="math-container">$rk(A)=O(d\ln|A|)$</span>, where <span class="math-container">$|A|$</span> is the number of <span class="math-container">$1$</span>s in <span class="math-container">$A$</span>. 
</blockquote>
<b>Proof:</b> 
Construct a random all-<span class="math-container">$1$</span> submatrix <span class="math-container">$R$</span> by picking each row independently with the same probability <span class="math-container">$p=1/(d+1)$</span>. Let <span class="math-container">$I$</span> be the obtained random subset of rows. Then let <span class="math-container">$R=I\times J$</span>, where <span class="math-container">$J$</span> is the set of all columns of <span class="math-container">$A$</span> that have no zeros in the rows in <span class="math-container">$I$</span>.
<p>
<p>A <span class="math-container">$1$</span>-entry <span class="math-container">$(i,j)$</span> of <span class="math-container">$A$</span> is covered by <span class="math-container">$R$</span> if <span class="math-container">$i$</span> was chosen in
<span class="math-container">$I$</span> and none of (at most <span class="math-container">$d$</span>) rows with a <span class="math-container">$0$</span> in the <span class="math-container">$j$</span>-th column
was chosen in <span class="math-container">$I$</span>. Hence, the entry <span class="math-container">$(i,j)$</span> is covered with probability at least <span class="math-container">$p(1-p)^{d}\geq pe^{-pd-p^2d}\geq p/e$</span>.
If we apply this procedure <span class="math-container">$r$</span> times to get <span class="math-container">$r$</span> rectangles,
then the probability that <span class="math-container">$(i,j)$</span> is covered by none of these
rectangles does not exceed <span class="math-container">$(1-p/e)^r\leq e^{-rp/e}$</span>.  By the union bound, the
probability that some <span class="math-container">$1$</span>-entry of <span class="math-container">$A$</span> remains uncovered is at most
<span class="math-container">$|A|\cdot e^{-rp/e}$</span>, which is smaller than <span class="math-container">$1$</span> for <span class="math-container">$r=O(d\ln|A|)$</span>.
<span class="math-container">$\Box$</span></p>
<blockquote>
<b>Corollary:</b> If every column or every row of a boolean matrix <span class="math-container">$A$</span> contains at most <span class="math-container">$d$</span> zeros, then the mapping <span class="math-container">$y=Ax$</span> can be computed by an unbounded fanin OR-circuit of depth-3 using 
<span class="math-container">$O(dn)$</span> wires.
</blockquote>
<p>I guess that a similar upper bound as in Lemma 2 should also hold when <span class="math-container">$d$</span> is the average number of <span class="math-container">$1$</span>s in a column (or in a row). It would be interesting to show this.</p>
<hr>
<p><b>Remark:</b> (added 04.01.2018) An analogue <span class="math-container">$rk(A)=O(d^2\log n)$</span> of Lemma 2 also holds when <span class="math-container">$d$</span> is the <b>maximum average number</b> of zeros in a submatrix of <span class="math-container">$A$</span>, where the <i>average number</i> of zeros in an <span class="math-container">$r\times s$</span> matrix is the total number of zeros divided by <span class="math-container">$s+r$</span>.
This follows from  Theorem 2 in <a href="https://link.springer.com/article/10.1007/BF01300127" rel="nofollow noreferrer">N. Eaton and V. Rödl;, Graphs of small dimension, <i>Combinatorica</i> 16(1) (1996) 59-85</a>.
A slightly worse upper bound <span class="math-container">$rk(A)=O(d^2\ln^2 n)$</span> can be derived directly from Lemma 2 as follows.</p>
<p>
<blockquote>
<b>Lemma 3:</b> Let <span class="math-container">$d\geq 1$</span>. If every spanning subgraph of a bipartite graph <span class="math-container">$G$</span> has average degree <span class="math-container">$\leq d$</span>, then <span class="math-container">$G$</span> can be written as a union <span class="math-container">$G=G_1\cup G_2$</span>, where the maximum left degree of <span class="math-container">$G_1$</span> and the maximum right degree of <span class="math-container">$G_2$</span> are <span class="math-container">$\leq d$</span>.
</blockquote>
<p><b>Proof:</b> Induction on the number <span class="math-container">$n$</span> of vertices. The base cases <span class="math-container">$n=1$</span> and <span class="math-container">$n=2$</span> are obvious. For the induction step, we will color the edges in blue and red so that the maximum degree in both blue and red subgraphs are <span class="math-container">$\leq d$</span>. Take a vertex <span class="math-container">$u$</span> of degree <span class="math-container">$\leq d$</span>; such a vertex must exists because also the average degree of the entire graph must be <span class="math-container">$\leq d$</span>. If <span class="math-container">$u$</span> belongs to the left part, then color all edges incident to <span class="math-container">$u$</span> in blue, else color all these edges in red. If we remove the vertex <span class="math-container">$u$</span> then the average degree of the resulting graph <span class="math-container">$G$</span> is also at most <span class="math-container">$d$</span>, and we can color the edges of this graph by the induction hypothesis. <span class="math-container">$\Box$</span></p>
<blockquote>
<b>Lemma 4:</b> Let <span class="math-container">$d\geq 1$</span>. If the maximum average number of zeros in a boolean <span class="math-container">$n\times n$</span> matrix <span class="math-container">$A=(a_{i,j})$</span> is at most <span class="math-container">$d$</span>, then <span class="math-container">$rk(A)=O(d^2\ln^2 n)$</span>.
</blockquote>
<p><b>Proof:</b> Consider the bipartite <span class="math-container">$n\times n$</span> graph <span class="math-container">$G$</span> with <span class="math-container">$(i,j)$</span> being an edge iff <span class="math-container">$a_{i,j}=0$</span>. Then the maximum average degree of <span class="math-container">$G$</span> is at most <span class="math-container">$d$</span>. By Lemma 3, we can write <span class="math-container">$G=G_1\cup G_2$</span>, where
the maximum degree of the vertices on the left part of <span class="math-container">$G_1$</span>, and the maximum degree of the vertices on the right part of <span class="math-container">$G_2$</span> is <span class="math-container">$\leq d$</span>.
Let <span class="math-container">$A_1$</span> and <span class="math-container">$A_2$</span> be the complements of the adjacency matrices of <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span>.
Hence, <span class="math-container">$A= A_1\land A_2$</span> is a componentwise AND of these matrices.
The maximum number of zeros in every row of <span class="math-container">$A_1$</span> and in every column of <span class="math-container">$A_2$</span> is at most <span class="math-container">$d$</span>. Since <span class="math-container">$rk(A)\leq rk(A_1)\cdot rk(A_2)$</span>, Lemma 2 yields <span class="math-container">$rk(A)=O(d^2\ln^2 n)$</span>. <span class="math-container">$\Box$</span></p>
<p> 
<b>N.B.</b> The following simple example (pointed by Igor Sergeev) shows that my "guess" at the end of the answer was totally wrong: if we take <span class="math-container">$d=d(A)$</span> to be the average number of zeros in the <b>entire</b> matrix <span class="math-container">$A$</span> (not the maximum of averages over all submatrices), then Lemma 2 can badly fail.  Let <span class="math-container">$m=\sqrt{n}$</span>, and put an identity <span class="math-container">$m\times m$</span> matrix in, say left upper corner of <span class="math-container">$A$</span>, and fill the remaining entries by ones. Then <span class="math-container">$d(A)\leq m^2/2n &lt; 1$</span> but <span class="math-container">$rk(A)\geq m$</span>, which is <i>exponentially</i> larger than <span class="math-container">$\ln|A|$</span>. Note, however, that the OR complexity of this matrix is very small, is <span class="math-container">$O(n)$</span>. So, <i>direct</i> arguments (not via rank) <i>can</i> yield much better upper bounds on the OR complexity of dense matrices.

CC BY-SA 3.0
2018-01-03T10:14:04.203Z
Thanks a lot, Stasys! This is nice! In the meantime, Ivan Mihajlin came with another proof. I've posted it below.
Alexander S. Kulikov
CC BY-SA 4.0
2018-01-01T16:07:46.197Z
2021-12-16T09:59:41.207Z
2021-12-16T09:59:41.207Z
Stasys
<p>Consider the following simple monotone circuit model: each gate is just a binary OR. What is the complexity of a function $f(x)=Ax$ where $A$ is a Boolean $n \times n$ matrix with $O(n)$ 0's? Can it be computed by linear size OR-circuits?</p>

<p>More formally, $f$ is a function from $n$ to $n$ bits. The $i$-th output of $f$ is $\bigvee_{j=1}^{n}(A_{ij} \land x_j)$ (i.e., an OR of the subset of input bits given by the $i$-th row of $A$).</p>

<p>Note that $O(n)$ 0's split the rows of $A$ into $O(n)$ ranges (subsets consisting of consecutive elements of $[n]$). This makes it possible to employ known range query data structures. E.g., a sparse table data structure can be turned into an OR-circuit of size $O(n\log n)$. <a href="https://en.wikipedia.org/wiki/Range_query_(data_structures)#Semigroup_operators" rel="noreferrer">Yao's algorithm</a> for range semigroup operator queries can be turned into an almost linear circuit (of size $O(\alpha(n) \cdot n)$ where $\alpha(n)$ is inverse Ackermann)</p>

<p>In particular, I don't even know how to construct a linear size circuit for a special case where each row of $A$ contains exactly two zeros. While the case of exactly one zero in each row is easy. (Each output function can be computed by an OR of a prefix $[1..k-1]$ and a suffix $[k+1..n]$, which can be precomputed by $2n$ OR-gates.)</p>

CC BY-SA 3.0
2017-12-30T22:24:53.350Z
One upper bound is known: it is at most rk(A) times n divided by log n, where rk(A) is the OR-rank of a boolean matrix A (= minimum number of all-1 submatrices whose OR coincides with A). See Lemma 2.5 in [this book](http://lovelace.thi.informatik.uni-frankfurt.de/~jukna/Knizka/). So, how large (at most) the boolean rank of an nxn matrix with O(n) zeroes can be?
Stasys
CC BY-SA 3.0
2017-12-31T09:58:44.893Z
@Stasys Thank you, Stasys! Already for the matrix with zero diagonal the OR-rank is linear, right?
Alexander S. Kulikov
CC BY-SA 3.0
2017-12-31T13:15:44.770Z
The OR rank of your matrix (zero diagonal, and 1s elsewhere) is at most 2\log n: label rows/columns by binary strings of length \log n, and consider rectangles {(r,c) : r(i)=a, c(i)=1-a} for a=0,1. Note also that Lemma 2.5 is an *upper* bound. A *lower* bound in terms of OR rank is given in Thm. 3.20. Also, log of OR rank is exactly the nondeterministic communication complexity of matrices.
Stasys
CC BY-SA 3.0
2018-01-03T09:44:34.330Z
@Stasys oh, yes, right!
Alexander S. Kulikov
<ds.algorithms><circuit-complexity><upper-bounds>
OR-circuit complexity of a dense linear operator
Alexander S. Kulikov
# OR-circuit complexity of a dense linear operator

(Asked by: username_0 on 2017-12-30)

Consider the following simple monotone circuit model: each gate is just a binary OR. What is the complexity of a function $f(x)=Ax$ where $A$ is a Boolean $n \times n$ matrix with $O(n)$ 0's? Can it be computed by linear size OR-circuits?

More formally, $f$ is a function from $n$ to $n$ bits. The $i$-th output of $f$ is $\bigvee\_{j=1}^{n}(A\_{ij} \land x\_j)$ (i.e., an OR of the subset of input bits given by the $i$-th row of $A$).

Note that $O(n)$ 0's split the rows of $A$ into $O(n)$ ranges (subsets consisting of consecutive elements of $[n]$). This makes it possible to employ known range query data structures. E.g., a sparse table data structure can be turned into an OR-circuit of size $O(n\log n)$. [Yao's algorithm](https://en.wikipedia.org/wiki/Range_query_(data_structures)#Semigroup_operators) for range semigroup operator queries can be turned into an almost linear circuit (of size $O(\alpha(n) \cdot n)$ where $\alpha(n)$ is inverse Ackermann)

In particular, I don't even know how to construct a linear size circuit for a special case where each row of $A$ contains exactly two zeros. While the case of exactly one zero in each row is easy. (Each output function can be computed by an OR of a prefix $[1..k-1]$ and a suffix $[k+1..n]$, which can be precomputed by $2n$ OR-gates.)

**Tags:** ds.algorithms, circuit-complexity, upper-bounds
> **Comments:**
> **username_1**: One upper bound is known: it is at most rk(A) times n divided by log n, where rk(A) is the OR-rank of a boolean matrix A (= minimum number of all-1 submatrices whose OR coincides with A). See Lemma 2.5 in [this book](http://lovelace.thi.informatik.uni-frankfurt.de/~jukna/Knizka/). So, how large (at most) the boolean rank of an nxn matrix with O(n) zeroes can be?  
> **username_0**: @Stasys Thank you, Stasys! Already for the matrix with zero diagonal the OR-rank is linear, right?  
> **username_1**: The OR rank of your matrix (zero diagonal, and 1s elsewhere) is at most 2\log n: label rows/columns by binary strings of length \log n, and consider rectangles {(r,c) : r(i)=a, c(i)=1-a} for a=0,1. Note also that Lemma 2.5 is an *upper* bound. A *lower* bound in terms of OR rank is given in Thm. 3.20. Also, log of OR rank is exactly the nondeterministic communication complexity of matrices.  
> **username_0**: @Stasys oh, yes, right!  

---

## 2 answers

### Answer by username_1 on 2018-01-01. Score: 7 | Accepted answer

This is a partial (affirmative) answer in the case when we have an upper bound on the number of zeros in every row or in every column.

A *rectangle* is a boolean matrix consisting of one all-1 submatrix and having zeros elsewhere.
An OR-rank $rk(A)$ of a boolean matrix is the smallest number $r$ of
rectangles such that $A$ can be written as a (componentwise) OR of these rectangles. That is, every 1-entry of $A$ is a 1-entry in at least one of the rectangles, and every 0-entry of $A$ is a 0-entry in all rectangles. Note that $\log rk(A)$ is exactly the nondeterministic communication complexity of the matrix $A$ (where Alice gets rows, and Bob columns).
As OP wrote, every boolean $m\times n$ matrix $A=(a\_{i,j})$ defines a mapping $y=Ax$, where $y\_i=\bigvee\_{j=1}^na\_{i,j}x\_j$ for $i=1,\ldots,m$. That is, we take a matrix-vector product over the boolean semiring.

The following lemma is due to Pudlák and Rödl; see Proposition 10.1 in [this paper](http://www.sciencedirect.com/science/article/pii/0012365X9400115Y)
or Lemma 2.5 in [this book](https://web.vu.lt/mif/s.jukna//Knizka/) for a direct construction.

> **Lemma 1:** For every boolean $n\times n$ matrix $A$, the mapping $y=Ax$ can be computed by an unbounded fanin OR-circuit of depth-3 using at most $O(rk(A)\cdot n/\log n)$ wires.

We also have the following upper bound on the OR-rank of dense matrices.
The argument is a simple variation of that used by Alon in [this paper](http://www.math.tau.ac.il/%7Enogaa/PDFS/Publications/Covering%20graphs%20by%20the%20minimum%20number%20of%20equivalence%20relations.pdf).

> **Lemma 2:** If every column or every row of a boolean matrix $A$ contains at most $d$ zeros, then $rk(A)=O(d\ln|A|)$, where $|A|$ is the number of $1$s in $A$.

**Proof:**
Construct a random all-$1$ submatrix $R$ by picking each row independently with the same probability $p=1/(d+1)$. Let $I$ be the obtained random subset of rows. Then let $R=I\times J$, where $J$ is the set of all columns of $A$ that have no zeros in the rows in $I$.

A $1$-entry $(i,j)$ of $A$ is covered by $R$ if $i$ was chosen in
$I$ and none of (at most $d$) rows with a $0$ in the $j$-th column
was chosen in $I$. Hence, the entry $(i,j)$ is covered with probability at least $p(1-p)^{d}\geq pe^{-pd-p^2d}\geq p/e$.
If we apply this procedure $r$ times to get $r$ rectangles,
then the probability that $(i,j)$ is covered by none of these
rectangles does not exceed $(1-p/e)^r\leq e^{-rp/e}$. By the union bound, the
probability that some $1$-entry of $A$ remains uncovered is at most
$|A|\cdot e^{-rp/e}$, which is smaller than $1$ for $r=O(d\ln|A|)$.
$\Box$

> **Corollary:** If every column or every row of a boolean matrix $A$ contains at most $d$ zeros, then the mapping $y=Ax$ can be computed by an unbounded fanin OR-circuit of depth-3 using
> $O(dn)$ wires.

I guess that a similar upper bound as in Lemma 2 should also hold when $d$ is the average number of $1$s in a column (or in a row). It would be interesting to show this.

---

**Remark:** (added 04.01.2018) An analogue $rk(A)=O(d^2\log n)$ of Lemma 2 also holds when $d$ is the **maximum average number** of zeros in a submatrix of $A$, where the *average number* of zeros in an $r\times s$ matrix is the total number of zeros divided by $s+r$.
This follows from Theorem 2 in [N. Eaton and V. Rödl;, Graphs of small dimension, *Combinatorica* 16(1) (1996) 59-85](https://link.springer.com/article/10.1007/BF01300127).
A slightly worse upper bound $rk(A)=O(d^2\ln^2 n)$ can be derived directly from Lemma 2 as follows.

> **Lemma 3:** Let $d\geq 1$. If every spanning subgraph of a bipartite graph $G$ has average degree $\leq d$, then $G$ can be written as a union $G=G\_1\cup G\_2$, where the maximum left degree of $G\_1$ and the maximum right degree of $G\_2$ are $\leq d$.

**Proof:** Induction on the number $n$ of vertices. The base cases $n=1$ and $n=2$ are obvious. For the induction step, we will color the edges in blue and red so that the maximum degree in both blue and red subgraphs are $\leq d$. Take a vertex $u$ of degree $\leq d$; such a vertex must exists because also the average degree of the entire graph must be $\leq d$. If $u$ belongs to the left part, then color all edges incident to $u$ in blue, else color all these edges in red. If we remove the vertex $u$ then the average degree of the resulting graph $G$ is also at most $d$, and we can color the edges of this graph by the induction hypothesis. $\Box$

> **Lemma 4:** Let $d\geq 1$. If the maximum average number of zeros in a boolean $n\times n$ matrix $A=(a\_{i,j})$ is at most $d$, then $rk(A)=O(d^2\ln^2 n)$.

**Proof:** Consider the bipartite $n\times n$ graph $G$ with $(i,j)$ being an edge iff $a\_{i,j}=0$. Then the maximum average degree of $G$ is at most $d$. By Lemma 3, we can write $G=G\_1\cup G\_2$, where
the maximum degree of the vertices on the left part of $G\_1$, and the maximum degree of the vertices on the right part of $G\_2$ is $\leq d$.
Let $A\_1$ and $A\_2$ be the complements of the adjacency matrices of $G\_1$ and $G\_2$.
Hence, $A= A\_1\land A\_2$ is a componentwise AND of these matrices.
The maximum number of zeros in every row of $A\_1$ and in every column of $A\_2$ is at most $d$. Since $rk(A)\leq rk(A\_1)\cdot rk(A\_2)$, Lemma 2 yields $rk(A)=O(d^2\ln^2 n)$. $\Box$

**N.B.** The following simple example (pointed by Igor Sergeev) shows that my "guess" at the end of the answer was totally wrong: if we take $d=d(A)$ to be the average number of zeros in the **entire** matrix $A$ (not the maximum of averages over all submatrices), then Lemma 2 can badly fail. Let $m=\sqrt{n}$, and put an identity $m\times m$ matrix in, say left upper corner of $A$, and fill the remaining entries by ones. Then $d(A)\leq m^2/2n < 1$ but $rk(A)\geq m$, which is *exponentially* larger than $\ln|A|$. Note, however, that the OR complexity of this matrix is very small, is $O(n)$. So, *direct* arguments (not via rank) *can* yield much better upper bounds on the OR complexity of dense matrices.

> **Comments:**
> **username_0**: Thanks a lot, Stasys! This is nice! In the meantime, Ivan Mihajlin came with another proof. I've posted it below.  

---

### Answer by username_0 on 2018-01-03. Score: 2

(I tried to post this as a comment to Stasys' answer above, but this text is too long for a comment, so posting it as an answer.) Ivan Mihajlin (@ivmihajlin) came up with the following construction. Similarly to Stasys' proof, it works for the case when the maximum (rather than average) number of 0’s in each row is bounded.

First, consider the case when every row contains exactly two zeros. Consider the following undirected graph: the set of vertices is $[n]$; two nodes $i$ and $j$ are joined by an edge, if there is a row having zeros in columns $i$ and $j$. The graph has $n$ edges and hence it contains a cut $(L,R)$ of size at least $n/2$. This cut splits the columns of the matrix into two parts ($L$ and $R$). Let now also split the rows into two parts: the top part $T$ contains all columns that have exactly one zero in both $L$ and $R$; the bottom part $B$ contains all the remaining rows. What is nice about the top part of the matrix ($T \times (L \cup R)$) is that it can be computed by $O(n)$ gates. For the bottom part, let’s cut all-1 columns out of it and make a recursive call. The corresponding recurrence relation is $C(n) \le an + C(n/2)$ implying $C(n)=O(n)$.

Now, generalize it to the case of at most $d$ zeros in every row. Let $C\_d(n)$ be the complexity of an $n \times (\le dn)$ matrix with at most $d$ zeros per row (if there are more than $dn$ columns, then some of them are all-1). Partition the columns into two parts $L$ and $R$ such that at least $n(1-2^{-d})$ rows (call them $T$) satisfy the following property: if there are exactly $d$ zeroes in a row, then not all of them belong to the same part (denote the remaining rows by $B$). Then make three recursive calls: $T \times L$, $T \times R$, and $B \times (L \cup R)$. This gives a recurrence relation $C\_d(n) \le an + 2\cdot C\_{d-1}(n(1-2^{-d}))+C\_d(2^{-d}n)$. This, in turn, implies that $C\_d(n) \le f(d)\cdot n$. The function $f(d)$ is exponential, but still.

> **Comments:**
> **username_1**: A nice argument. But it seems to be tailor made for the case of d=2 zeros per row. What about d>2 zeros?  
> **username_0**: @Stasys, it is doable if I'm not mistaken. I've updated the answer.  

---

