A square in a matrix is its $2\times 2$ submatrix.
Lemma: Let $A$ be an $n\times n$ matrix with $|A|\geq 2n^{3/2}$ ones. Then $A$ contains at least $\Omega(|A|/n)^4$ all-$1$ squares.Proof: Say that a row covers a pair $u$ of two columns, if this row has $1$s in these columns. If $a_i$ denotes the number of ones in the $i$-th row of $A$, then the number of pairs of columns covered by the rows of $A$ is \[ M=\sum_{i=1}^n \binom{a_i}{2}\geq n\binom{\sum_i a_i/n}{2} =n\binom{|A|/n}{2} \geqslant \frac{|A|^2}{2n}-\frac{|A|}{2} \geq \frac{|A|^2}{4n}\,. \] Now let $b_u$ be the number of rows covering the pair $u$ of columns. Then $\sum_u b_u=M$. Thus, the number of all-$1$ squares in $A$ is \begin{align*} \sum_u \binom{b_u}{2}&\geq \binom{n}{2}\binom{\sum_u b_u/\tbinom{n}{2}}{2} =\binom{n}{2}\binom{M/\tbinom{n}{2}}{2}\\ &\geq \frac{M^2}{2\tbinom{n}{2}} - \frac{M}{2} \geq \frac{M^2}{4\tbinom{n}{2}} \Geq \Big(\frac{|A|}{n} \Big)^4\,, \end{align*} where the $3$rd inequality holds because $M\geq |A|^2/4n\geq n^2>2\tbinom{n}{2}$. $\Box$
Given a boolean $n\times n$ matrix $A$, construct a boolean $N\times N$ matrix $B$ with $N=\binom{n}{2}$ as follows. The rows and columns of $B$ are labeled by $2$-element subsets $a$ of $[n]=\{1,\ldots,n\}$, and $B[a,b]=1$ iff $a\times b$ forms an all-$1$ square in $A$.
Recall that a Boolean matrix is $k$-free if it contains no $k\times k$ all-$1$ submatrices.
Observation: If $A$ is $k$-free, then $B$ is $K$-free for $K=\binom{k-1}{2}+1$.Proof: Suppose that $B$ has an all-$1$ submatrix of dimensions $|S|\times|T|$ with $S,T\subseteq \binom{[n]}{2}$ and $|S|,|T|\geq K$. This corresponds to a $|\cup S|\times |\cup T|$ all-$1$ submatrix in $A$. Since $\binom{m}{2}\geq \binom{k-1}{2}+1$ holds only if $m\geq k$, we have $|\cup S|\geq k$ and $|\cup T|\geq k$, contradicting the $k$-freeness of $A$. $\Box$
Theorem: If $A$ is $k$-free, then $\OR(\overline{B})=O(n^2)$ but \[ \OR(B)\Geq \Big(\frac{|A|}{kn}\Big)^4\,. \]Proof: By Lemma, $B$ has $|B|\geqslant (|A|/n)^4$ ones. By the Observation, $B$ is $K$-free for $K=\Theta(k^2)$. Thus, Nechiporuk's theorem (Theorem 3.9 in the book), yields \[ \OR(B)\geq \frac{|B|}{K^2} \Geq \Big(\frac{|A|}{kn}\Big)^4\,. \] It therefore remains to construct an OR circuit for $\overline{B}$ of size $O(n^2)$. For this, observe that $\overline{B}[a,b]=1$ iff the submatrix $a\times b$ of $\overline{A}$ contains at least one $1$. Thus, we can take a depth-$3$ circuit where the nodes on the second and the third layer are numbers $1,\ldots,n$, and there is a wire joining an input or output $a$ with a node $i$ iff $i\in a$. The wires between the second and the third levels are drown according to the entries of the matrix $\overline{A}$. The entire circuit has $O(n^2)$ wires, as desired. $\Box$
Applications: