OR-circuit complexity of a dense linear operator 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 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.)
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&aacute;k and R&#246;dl; see Proposition 10.1 in this paper
or Lemma 2.5 in this book 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.


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&#246;dl;, Graphs of small dimension, Combinatorica 16(1) (1996) 59-85.
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 &lt; 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.