  We relate two complexity notions of bipartite graphs: the minimal weight
biclique covering number $\mathrm{Cov}(G)$ and the minimal rectifier network
size $\mathrm{Rect}(G)$ of a bipartite graph $G$. We show that there exist
graphs with $\mathrm{Cov}(G)\geq \mathrm{Rect}(G)^{3/2-\epsilon}$. As a
corollary, we establish that there exist nondeterministic finite automata
(NFAs) with $\varepsilon$-transitions, having $n$ transitions total such that
the smallest equivalent $\varepsilon$-free NFA has $\Omega(n^{3/2-\epsilon})$
transitions. We also formulate a version of previous bounds for the weighted
set cover problem and discuss its connections to giving upper bounds for the
possible blow-up.
