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

详细信息    查看全文

• 作者：Szabolcs Iván (18)
  ádám D. Lelkes (19)
  Judit Nagy-Gy?rgy (18)
  Balázs Sz?rényi (20) (21)
  Gy?rgy Turán (19) (20)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8614
• 期：1
• 页码：174-185
• 全文大小：264 KB
• 参考文献：1. Berman, P., Bhattacharyya, A., Grigorescu, E., Raskhodnikova, S., Woodruff, D.P., Yaroslavtsev, G.: Steiner transitive-closure spanners of low-dimensional posets. Combinatorica, 1-4 (2014)
  2. Blum, N.: More on the power of chain rules in context-free grammars. Theoretical Computer Science?27(3), 287-95 (1983), Special Issue Ninth International Colloquium on Automata, Languages and Programming (ICALP), Aarhus, Summer (1982)
  3. Hromkovic, J., Schnitger, G.: Comparing the size of NFAs with and without / ε-transitions. Theor. Comput. Sci.?380(1-2), 100-14 (2007) CrossRef
  4. Hromkovic, J., Seibert, S., Wilke, T.: Translating regular expressions into small epsilon-free nondeterministic finite automata. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol.?1200, pp. 55-6. Springer, Heidelberg (1997) CrossRef
  5. Jukna, S.: Boolean Function Complexity - Advances and Frontiers. Algorithms and combinatorics, vol.?27. Springer (2012)
  6. Jukna, S.: Computational complexity of graphs. In: Dehmer, M., Emmert-Streib, F. (eds.) Advances in Network Complexity, pp. 99-53. Wiley (2013)
  7. Jukna, S., Sergeev, I.: Complexity of linear Boolean operators. Foundations and Trends in Theoretical Computer Science?9(1), 1-23 (2013) CrossRef
  8. Kollár, J., Rónyai, L., Szabó, T.: Norm-graphs and bipartite Turán numbers. Combinatorica?16(3), 399-06 (1996) CrossRef
  9. Lovász, L.: A kombinatorika minimax tételeir?l. Matematikai Lapok?26, 209-64 (1975)
  10. Lupanov, O.B.: On rectifier and switching-and-rectifier schemes. Dokl. Akad. Nauk SSSR?111, 1171-174 (1956)
  11. Mehlhorn, K.: Some remarks on Boolean sums. In: Becvar, J. (ed.) MFCS 1979. LNCS, vol.?74, pp. 375-80. Springer, Heidelberg (1979) CrossRef
  12. Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: SWAT (FOCS), pp. 188-91. IEEE Computer Society (1971)
  13. Nechiporuk, E.I.: On a Boolean matrix. Systems Theory Res.?21, 236-39 (1971)
  14. Pippenger, N., Valiant, L.G.: Shifting graphs and their applications. J. ACM?23(3), 423-32 (1976) CrossRef
  15. Schnitger, G.: Regular expressions and nFAs without / e-transitions. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.?3884, pp. 432-43. Springer, Heidelberg (2006) CrossRef
  16. Wegener, I.: A new lower bound on the monotone network complexity of Boolean sums. Acta Informatica?13(2), 109-14 (1980) CrossRef
  17. Wegener, I.: The Complexity of Boolean Functions. John Wiley & Sons, Inc., New York (1987)
  18. Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms, 1st edn. Cambridge University Press, New York (2011) CrossRef
  
• 作者单位：Szabolcs Iván (18)
  ádám D. Lelkes (19)
  Judit Nagy-Gy?rgy (18)
  Balázs Sz?rényi (20) (21)
  Gy?rgy Turán (19) (20)
  
  18. University of Szeged, Hungary
  19. University of Illinois at Chicago, USA
  20. MTA-SZTE Research Group on Artificial Intelligence, Szeged, Hungary
  21. SequeL Project, INRIA Lille, France
  
• ISSN：1611-3349

文摘

We relate two complexity notions of bipartite graphs: the minimal weight biclique covering number Cov(G) and the minimal rectifier network size Rect(G) of a bipartite graph G. We show that there exist graphs with Cov(G)?≥-em class="a-plus-plus">Rect(G)3/2??-em class="a-plus-plus">ε . As a corollary, we establish that there exist nondeterministic finite automata (NFAs) with ε-transitions, having n transitions total such that the smallest equivalent ε-free NFA has Ω(n 3/2??-em class="a-plus-plus">ε ) 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.