{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:37Z","timestamp":1725663277614},"publisher-location":"Berlin, Heidelberg","reference-count":8,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540083535"},{"type":"electronic","value":"9783540372851"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1977]]},"DOI":"10.1007\/3-540-08353-7_169","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T16:25:42Z","timestamp":1330187142000},"page":"465-474","source":"Crossref","is-referenced-by-count":0,"title":["How good is the adversary lower bound ?"],"prefix":"10.1007","author":[{"given":"Peter","family":"Ru\u017ei\u010dka","sequence":"first","affiliation":[]},{"given":"Juraj","family":"Wiedermann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,24]]},"reference":[{"key":"47_CR1","doi-asserted-by":"crossref","unstructured":"Dobkin, D., Lipton, R., On the Complexity of Computations under Varying Sets of Primitives. Automata Theory and Formal Languages 2nd GI Conference, Lecture Notes in Computer Science 33, Springer-Verlag (1975), 110\u2013117.","DOI":"10.1007\/3-540-07407-4_14"},{"key":"47_CR2","volume-title":"The Art of Computer Programming, Vol. 3, Sorting and Searching","author":"D. E. Knuth","year":"1973","unstructured":"Knuth, D.E., The Art of Computer Programming, Vol. 3, Sorting and Searching, Addison-Wesley, Reading, Mass., 1973."},{"key":"47_CR3","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0304-3975(76)90078-5","volume":"1","author":"M. L. Fredman","year":"1976","unstructured":"Fredman, M.L., How Good is the Information Theory Bound for Sorting? Theoretical Computer Science 1 (1976), 355\u2013361.","journal-title":"Theoretical Computer Science"},{"key":"47_CR4","unstructured":"Kirkpatrick, D.G., Topics in the Complexity of Combinatorial Algorithms. Department of Computer Science, University of Toronto, Technical Report No. 74, 1974."},{"key":"47_CR5","first-page":"639","volume":"6","author":"M. O. Rabin","year":"1972","unstructured":"Rabin, M.O., Proving Simultaneous Positivity of Linear Forms, JCSS 6 (1972), 639\u2013650.","journal-title":"JCSS"},{"key":"47_CR6","doi-asserted-by":"crossref","unstructured":"Reingold, E.M., Computing the Maxima and the Median, 12th Annual Symposium on Switching and Automata Theory (1971), 216\u2013218.","DOI":"10.1109\/SWAT.1971.9"},{"key":"47_CR7","unstructured":"Ru\u017ei\u010dka, P., The Influence of Arithmetics on the Complexity of Comparison Problems, Computing Research Centre, Bratislava, Technical Report (1977), 10\u201319 (in Slovak)."},{"key":"47_CR8","doi-asserted-by":"crossref","unstructured":"Yao, A. Ch., On the Complexity of Comparison Problems Using Linear Functions, 16th Annual Symposium on Foundations of Computer Science, (1976), 85\u201389.","DOI":"10.1109\/SFCS.1975.20"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1977"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-08353-7_169.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:59:25Z","timestamp":1605643165000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-08353-7_169"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977]]},"ISBN":["9783540083535","9783540372851"],"references-count":8,"URL":"https:\/\/doi.org\/10.1007\/3-540-08353-7_169","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1977]]}}}