{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T21:56:32Z","timestamp":1775512592204,"version":"3.50.1"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1991,6,1]],"date-time":"1991-06-01T00:00:00Z","timestamp":675734400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1991,6]]},"DOI":"10.1007\/bf01206357","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T14:33:38Z","timestamp":1109255618000},"page":"131-143","source":"Crossref","is-referenced-by-count":16,"title":["An ?(n 4\/3) lower bound on the randomized complexity of graph properties"],"prefix":"10.1007","volume":"11","author":[{"given":"P\ufffdter","family":"Hajnal","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"D. Angluin, andL. G. Valiant: Fast probabilistic algorithms for Hamiltonian circuits and matchings,Journal of Computer and System Sciences,19, 155?193.","DOI":"10.1016\/0022-0000(79)90045-X"},{"key":"CR2","unstructured":"B. Bollob\ufffds:Extremal Graph theory, Chapter VIII., Academic Press, 1978."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0012-365X(74)90119-8","volume":"10","author":"P. A. Catlin","year":"1974","unstructured":"P. A. Catlin: Subgraphs of graphs I.,Discrete Math. 10 (1974), 225?233.","journal-title":"Discrete Math."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"H. Chernoff: A measure of asymptotic effiency for tests of a hypothesis based on the sum of observations,Annals of Math. Stat.,23 (1952), 493?509.","journal-title":"Annals of Math. Stat."},{"issue":"1","key":"CR5","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF01375470","volume":"11","author":"V. King","year":"1991","unstructured":"V. King: An ?(n 5\/4) lower bound on the randomized complexity of graph properties,Combinatorica,11 (1) (1991), 47?56.","journal-title":"Combinatorica"},{"issue":"4","key":"CR6","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/BF02579140","volume":"4","author":"J. Kahn","year":"1984","unstructured":"J. Kahn, M. Saks, andD. Sturtevant: A topological aproach to evasiveness,Combinatorica,4(4) (1984), 297?306.","journal-title":"Combinatorica"},{"key":"CR7","unstructured":"L. Lov\ufffdsz:Combinatorial Problems and Exercises, North-Holland 1979."},{"issue":"4","key":"CR8","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/1008299.1008302","volume":"5","author":"A. L. Rosenberg","year":"1973","unstructured":"A. L. Rosenberg: On the time required to recognize properties of graphs: A problem,SIGACT News,5 (4) (1973), 15?16.","journal-title":"SIGACT News"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"R. Rivest, andJ. Vuillemin: A generalization and proof of the Aanderaa-Rosenberg conjecture,Proc. 7th SIGACT Conference, (1975), ACM 1976.","DOI":"10.1145\/800116.803747"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0095-8956(78)90005-9","volume":"25","author":"N. Sauer","year":"1978","unstructured":"N. Sauer, andJ. Spencer: Edge-disjoint replacement of graphs,J. of Combinatorial Theory Ser. B25 (1978), 295?302.","journal-title":"J. of Combinatorial Theory Ser. B"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"A. Yao: Probabilistic computation: towards a unified measure of complexity,Proc. 18th IEEE FOCS, 1977, pp. 222?227.","DOI":"10.1109\/SFCS.1977.24"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"A. Yao: Lower bounds to randomized algorithms for graph properties,Proc. 28th IEEE FOCS, 1987, pp. 393?400.","DOI":"10.1109\/SFCS.1987.39"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01206357.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01206357\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01206357","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T22:41:34Z","timestamp":1586126494000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01206357"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,6]]}},"alternative-id":["BF01206357"],"URL":"https:\/\/doi.org\/10.1007\/bf01206357","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}