Abstract

We relate two complexity notions of bipartite graphs: the minimal weight biclique covering number Cov(G)\mathrm{Cov}(G) and the minimal rectifier network size Rect(G)\mathrm{Rect}(G) of a bipartite graph GG. We show that there exist graphs with Cov(G)≥Rect(G)3/2−ε\mathrm{Cov}(G)\geq \mathrm{Rect}(G)^{3/2-ε}. As a corollary, we establish that there exist nondeterministic finite automata (NFAs) with ε\varepsilon-transitions, having nn transitions total such that the smallest equivalent ε\varepsilon-free NFA has Ω(n3/2−ε)Ω(n^{3/2-ε}) 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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.