Biclique Coverings, Rectifier Networks and the Cost of ε-Removal

Szabolcs Iván 1 Ádám D. Lelkes 2 Judit Nagy-György 1 Balázs Szörényi 3, 1 György Turán 4, 2
1 University of Szeged [Szeged]
2 UIC - Department of Mathematics, Statistics and Computer Science [Chicago]
3 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
4 MTA-SZTE Research Group on Artificial Intelligence
Abstract : We relate two complexity notions of bipartite graphs: the minimal weight biclique covering number Cov(G) and the minimal rec-tifier network size Rect(G) of a bipartite graph G. We show that there exist graphs with Cov(G) ≥ Rect(G) 3/2−ǫ . As a corollary, we estab-lish that there exist nondeterministic finite automata (NFAs) with ε-transitions, having n transitions total such that the smallest equivalent ε-free NFA has Ω(n 3/2−ǫ) transitions. We also formulate a version of previous bounds for the weighted set cover problem and discuss its con-nections to giving upper bounds for the possible blow-up.
Type de document :
Communication dans un congrès
16th International Workshop on Descriptional Complexity of Formal Systems, Proceedings, Aug 2014, Turku, Finland. pp.174 - 185, 2014, 〈10.1007/978-3-319-09704-6_16〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01079368
Contributeur : Balazs Szorenyi <>
Soumis le : samedi 1 novembre 2014 - 11:39:51
Dernière modification le : samedi 7 avril 2018 - 14:30:02
Document(s) archivé(s) le : lundi 2 février 2015 - 16:51:59

Fichier

1406.0017v1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

UNIV-LILLE3 | INRIA | LAGIS | TDS-MACS

Citation

Szabolcs Iván, Ádám D. Lelkes, Judit Nagy-György, Balázs Szörényi, György Turán. Biclique Coverings, Rectifier Networks and the Cost of ε-Removal. 16th International Workshop on Descriptional Complexity of Formal Systems, Proceedings, Aug 2014, Turku, Finland. pp.174 - 185, 2014, 〈10.1007/978-3-319-09704-6_16〉. 〈hal-01079368〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

322

Téléchargements de fichiers

144

Contact


archive-ouverte@inria.fr