{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:06:01Z","timestamp":1775282761626,"version":"3.50.1"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1988,6,1]],"date-time":"1988-06-01T00:00:00Z","timestamp":581126400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1988,6,1]],"date-time":"1988-06-01T00:00:00Z","timestamp":581126400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[1988,6]]},"DOI":"10.1007\/bf00279952","type":"journal-article","created":{"date-parts":[[2023,7,4]],"date-time":"2023-07-04T16:42:15Z","timestamp":1688488935000},"page":"515-535","source":"Crossref","is-referenced-by-count":34,"title":["Graph complexity"],"prefix":"10.1007","volume":"25","author":[{"given":"Pavel","family":"Pudl\u00e1k","sequence":"first","affiliation":[]},{"given":"Vojt\u011bch","family":"R\u00f6dl","sequence":"additional","affiliation":[]},{"given":"Petr","family":"Savick\u00fd","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF00279952_CR1","doi-asserted-by":"crossref","unstructured":"Babai, L, Frankl, P., Simon, J.: Complexity classes in communication complexity, 27th FOCS, pp 337\u2013347 (1986)","DOI":"10.1109\/SFCS.1986.15"},{"key":"BF00279952_CR2","unstructured":"Babai, L., Pudl\u00e1k, P., R\u00f6dl, V., Szemeredi, E.: Lower bounds to the complexity of symmetric Boolean functions. Theor. Comput. Sci. (submitted for publication)"},{"key":"BF00279952_CR3","volume-title":"Graphs and hypergraphs","author":"C. Berge","year":"1973","unstructured":"Berge, C.: Graphs and hypergraphs. Amsterdam Oxford New York: North-Holland, American Elsevier 1973"},{"key":"BF00279952_CR4","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":"BF00279952_CR5","volume-title":"Probabilistic methods in combinatorics","author":"P. Erd\u00f6s","year":"1979","unstructured":"Erd\u00f6s, P., Spencer, J.: Probabilistic methods in combinatorics. Budapest: Akad\u00e9miai Kiad\u00f3 1979"},{"key":"BF00279952_CR6","unstructured":"Frankl, P., R\u00f6dl, V., Wilson, R.M.: The number of submatrices of given type in a Hadamard matrix and related results. J. Comb. Theor B (to appear)"},{"issue":"4","key":"BF00279952_CR7","first-page":"999","volume":"2","author":"E.T. Ne\u010diporuk","year":"1966","unstructured":"Ne\u010diporuk, E.T.: On a Boolean function. Sov Math Dokl 2, 4, 999\u20131000 (1966)","journal-title":"Sov Math Dokl"},{"key":"BF00279952_CR8","unstructured":"Razborov, A.A.: Formuly organi\u010denoj glubiny v bazise {&, \u2295} i nekotorye kombinatornye zada\u010di (Formulas of bounded depth in basis {&, \u2295} and some combinatorial problems), in Slo\u017enost' algoritmov i prikladnaja matemati\u010doeskaja logika, S.I. Adjan editor (1987)"},{"key":"BF00279952_CR9","volume-title":"The complexity of computing","author":"I.E. Savage","year":"1976","unstructured":"Savage, I.E.: The complexity of computing. New York: Wiley 1976"},{"key":"BF00279952_CR10","unstructured":"Sgall, J.: Personal communication (1987)"},{"key":"BF00279952_CR11","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-1 matrices. Combinatorica 4, 111\u2013116 (1984)","journal-title":"Combinatorica"},{"key":"BF00279952_CR12","series-title":"Lect. Notes Comput. Sci., vol. 176","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1007\/BFb0030339","volume-title":"Mathematical Foundations of Computer Science. Proceedings, 11th Symposium Praha, Czechoslovakia Sept. 3\u20137, 1984","author":"I. Wegener","year":"1984","unstructured":"Wegener, I.: On the complexity of slice functions. In: Chytil, M.P., Koubek, V. (eds.) Mathematical Foundations of Computer Science. Proceedings, 11th Symposium Praha, Czechoslovakia Sept. 3\u20137, 1984. (Lect. Notes Comput. Sci., vol. 176, pp. 553\u2013561) Berlin Heidelberg New York: Springer 1984"},{"key":"BF00279952_CR13","volume-title":"The complexity of Boolean functions","author":"I. Wegener","year":"1987","unstructured":"Wegener, I.: The complexity of Boolean functions. Stuttgart: B.G. Teubner\/New York: Wiley 1987"},{"key":"BF00279952_CR14","volume-title":"The theory of error-correcting codes","author":"F.J. MacWilliams","year":"1978","unstructured":"MacWilliams, F.J., Sloane, N.J.A.: The theory of error-correcting codes. Amsterdam New York: North-Holland 1978"},{"key":"BF00279952_CR15","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Some complexity questions related to distributive computing. Proc. 11th ACM STOC, pp 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00279952.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/BF00279952\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00279952.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,4]],"date-time":"2023-07-04T16:42:21Z","timestamp":1688488941000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BF00279952"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,6]]},"references-count":15,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1988,6]]}},"alternative-id":["BF00279952"],"URL":"https:\/\/doi.org\/10.1007\/bf00279952","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,6]]}}}