{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:16:03Z","timestamp":1753884963217},"publisher-location":"Berlin, Heidelberg","reference-count":8,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_24","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T02:29:04Z","timestamp":1193538544000},"page":"285-296","source":"Crossref","is-referenced-by-count":5,"title":["Improved Lower Bounds on the Randomized Complexity of Graph Properties"],"prefix":"10.1007","author":[{"given":"Amit","family":"Chakrabarti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Subhash","family":"Khot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"24_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Spencer, J. H. The probabilistic method, Second Edition, Wiley-Interscience Series, 2000, Appendix A.","DOI":"10.1002\/0471722154"},{"key":"24_CR2","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B. Extremal Graph Theory, Academic Press, 1978, Chapter 8.","DOI":"10.1007\/978-1-4612-9967-7"},{"key":"24_CR3","first-page":"119","volume":"10","author":"H. D. Gr\u00f6ger","year":"1992","unstructured":"Gr\u00f6ger, H. D. On the randomized complexity of monotone graph properties, Acta Cybernetica, 10 (1992), 119\u2013127.","journal-title":"Acta Cybernetica"},{"key":"24_CR4","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/BF01206357","volume":"11","author":"P. Hajnal","year":"1991","unstructured":"Hajnal, P. An \u03a9(n 4\/3) lower bound on the randomized complexity of graph properties, Combinatorica, 11 (1991), 131\u2013143.","journal-title":"Combinatorica"},{"key":"24_CR5","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01285818","volume":"12","author":"P. Hajnal","year":"1992","unstructured":"Hajnal, P., Szegedy, M. On packing bipartite graphs, Combinatorica, 12 (1992), 295\u2013301.","journal-title":"Combinatorica"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"King, V. Lower bounds on the complexity of graph properties, Proc. 20th ACM STOC (1988), 468\u2013476.","DOI":"10.1145\/62212.62258"},{"key":"24_CR7","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/0304-3975(76)90053-0","volume":"3","author":"R.L. Rivest","year":"1976","unstructured":"Rivest, R.L., Vuillemin, J. On recognizing graph properties from adjacency matrices, Theoret. Comput. Sci., 3 (1976), 371\u2013384.","journal-title":"Theoret. Comput. Sci."},{"key":"24_CR8","doi-asserted-by":"crossref","unstructured":"Yao, A.C. Lower bounds to randomized algorithms for graph properties, Proc. 28th IEEE FOCS (1987), 393\u2013400.","DOI":"10.1109\/SFCS.1987.39"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T22:28:15Z","timestamp":1556922495000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":8,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_24","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}