  A rectifier network is a directed acyclic graph with distinguished sources
and sinks; it is said to compute a Boolean matrix $M$ that has a $1$ in the
entry $(i,j)$ iff there is a path from the $j$th source to the $i$th sink. The
smallest number of edges in a rectifier network computing $M$ is a classic
complexity measure on matrices, which has been studied for more than half a
century.
  We explore two well-known techniques that have hitherto found little to no
applications in this theory. Both of them build on a basic fact that depth-$2$
rectifier networks are essentially weighted coverings of Boolean matrices with
rectangles. We obtain new results by using fractional and greedy coverings
(defined in the standard way).
  First, we show that all fractional coverings of the so-called full triangular
matrix have cost at least $n\log n$. This provides (a fortiori) a new proof of
the tight lower bound on its depth-$2$ complexity (the exact value has been
known since 1965, but previous proofs are based on different arguments).
Second, we show that the greedy heuristic is instrumental in tightening the
upper bound on the depth-$2$ complexity of the Kneser-Sierpi\'nski
(disjointness) matrix. The previous upper bound is $O(n^{1.28})$, and we
improve it to $O(n^{1.17})$, while the best known lower bound is
$\Omega(n^{1.16})$. Third, using fractional coverings, we obtain a form of
direct product theorem that gives a lower bound on unbounded-depth complexity
of Kronecker (tensor) products of matrices. In this case, the greedy heuristic
shows (by an argument due to Lov\'asz) that our result is only a logarithmic
factor away from the "full" direct product theorem. Our second and third
results constitute progress on open problem 7.3 and resolve, up to a
logarithmic factor, open problem 7.5 from a recent book by Jukna and Sergeev
(in Foundations and Trends in Theoretical Computer Science (2013)).
