{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:52:28Z","timestamp":1725663148683},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540502418"},{"type":"electronic","value":"9783540459606"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1988]]},"DOI":"10.1007\/3-540-50241-6_35","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T15:18:23Z","timestamp":1330183103000},"page":"138-150","source":"Crossref","is-referenced-by-count":0,"title":["The conjunctive complexity of quadratic boolean functions"],"prefix":"10.1007","author":[{"given":"Katja","family":"Lenz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ingo","family":"Wegener","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"11_CR1","unstructured":"Alon,N. and Boppana,R.: The monotone complexity of Boolean functions, Techn. Rep., 1985."},{"key":"11_CR2","unstructured":"Bloniarz,P.: The complexity of monotone Boolean functions and an algorithm for finding shortest paths in a graph, Ph.D. Thesis, MIT, 1979."},{"key":"11_CR3","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1007\/BF00264314","volume":"23","author":"S. Bublitz","year":"1986","unstructured":"Bublitz, S.: Decomposition of graphs and monotone formula size of homogeneous functions, Acta Informatica 23, 689\u2013696, 1986.","journal-title":"Acta Informatica"},{"key":"11_CR4","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0012-365X(80)90109-0","volume":"3O","author":"F.R.K. Chung","year":"1980","unstructured":"Chung, F.R.K.: On the covering of graphs, Discrete Mathematics 3O, 89\u201393, 1980.","journal-title":"Discrete Mathematics"},{"key":"11_CR5","first-page":"463","volume":"2","author":"E. Erd\u00f6s","year":"1935","unstructured":"Erd\u00f6s, E. and Szekeres, G.: A combinatorial problem in geometry, Compositio Math. 2, 463\u2013470, 1935.","journal-title":"Compositio Math."},{"key":"11_CR6","first-page":"506","volume":"25","author":"J. Fiedman","year":"1984","unstructured":"Fiedman, J.: Constructing O(n log n) size monotone formulae for the k-th elementary symmetric function of n Boolean variables, 25. FOCS, 506\u2013515, 1984.","journal-title":"FOCS"},{"key":"11_CR7","unstructured":"Garey,M. and Johnson, D.: Computers and intractability:A guide to the theory of NP-completeness, W.H.Freeman, 1979."},{"key":"11_CR8","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. Johnson","year":"1974","unstructured":"Johnson, D.: Approximation algorithms for combinatorial problems, Journal of Computer and System Sciences 9, 256\u2013278,1974.","journal-title":"Journal of Computer and System Sciences"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Mirwald, R. and Schnorr, C.P.: The multiplicative complexity of quadratic Boolean forms, 28. FOCS, 1987, submitted to TCS.","DOI":"10.1109\/SFCS.1987.57"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Orlin, J.: Contentment in graph theory: covering graphs with cliques, unpublished, 1976.","DOI":"10.1016\/1385-7258(77)90055-5"},{"key":"11_CR11","first-page":"307","volume":"15","author":"S. Poljak","year":"1974","unstructured":"Poljak, S.: A node on stable sets and coloring of graphs, Comment. Math. Univ. Carolinae 15, 307\u2013309, 1974.","journal-title":"Comment. Math. Univ. Carolinae"},{"key":"11_CR12","unstructured":"Pudlak, P., R\u00f6dl, V. and Savick\u00fd,P.: Graph complexity, Techn. Rep., Univ. Prague, 1987."},{"key":"11_CR13","unstructured":"R\u00f6dl,V.: private communication (cited in [14])."},{"key":"11_CR14","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF02579163","volume":"4","author":"Z. Tuza","year":"1984","unstructured":"Tuza, Z.: Covering of graphs by complete bipartite subgraphs, complexity of 0\u20131 matrices, Combinatorica 4, 111\u2013116, 1984.","journal-title":"Combinatorica"},{"key":"11_CR15","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0304-3975(85)90209-9","volume":"38","author":"I. Wegener","year":"1985","unstructured":"Wegener, I.: On the complexity of slice functions, Theoretical Computer Science 38, 55\u201368, 1985.","journal-title":"Theoretical Computer Science"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Wegener,I.: The complexity of Boolean functions, Wiley-Teubner, 1987.","DOI":"10.1007\/3-540-18170-9_185"}],"container-title":["Lecture Notes in Computer Science","CSL '87"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-50241-6_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:17:42Z","timestamp":1605629862000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-50241-6_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988]]},"ISBN":["9783540502418","9783540459606"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-50241-6_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1988]]}}}