Biclique coverings, rectifier networks and the cost of   $\varepsilon$-removal
  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. 
Szabolcs Iv\'an, \'Ad\'am D\'aniel Lelkes, Judit Nagy-Gy\"orgy,   Bal\'azs Sz\"or\'enyi, Gy\"orgy Tur\'an
cs.FL cs.DM