{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:29:07Z","timestamp":1725488947620},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540744559"},{"type":"electronic","value":"9783540744566"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74456-6_62","type":"book-chapter","created":{"date-parts":[[2007,8,14]],"date-time":"2007-08-14T03:29:48Z","timestamp":1187062188000},"page":"703-714","source":"Crossref","is-referenced-by-count":0,"title":["Optimal Randomized Comparison Based Algorithms for Collision"],"prefix":"10.1007","author":[{"given":"Riko","family":"Jacob","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"62_CR1","first-page":"80","volume-title":"Proc. 15th Annual ACM Symposium on Theory of Computing","author":"M. Ben-Or","year":"1983","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proc. 15th Annual ACM Symposium on Theory of Computing, pp. 80\u201386. ACM Press, New York (1983)"},{"key":"62_CR2","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/0020-0190(94)00154-5","volume":"52","author":"R.B. Boppana","year":"1994","unstructured":"Boppana, R.B.: The decision-tree complexity of element distinctness. Inf. Process. Lett.\u00a052, 329\u2013331 (1994)","journal-title":"Inf. Process. Lett."},{"key":"62_CR3","doi-asserted-by":"publisher","first-page":"1324","DOI":"10.1137\/S0097539702402780","volume":"34","author":"H. Buhrman","year":"2005","unstructured":"Buhrman, H., D\u00fcrr, C., Heiligman, M., H\u00f8yer, P., Magniez, F., Santha, M., de Wolf, R.: Quantum algorithms for element distinctness. SIAM J. Comput.\u00a034, 1324\u20131330 (2005) (electronic)","journal-title":"SIAM J. Comput."},{"key":"62_CR4","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1145\/1008731.1008735","volume":"51","author":"S. Aaronson","year":"2004","unstructured":"Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. J. ACM\u00a051, 595\u2013605 (2004) (electronic)","journal-title":"J. ACM"},{"key":"62_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11586821_1","volume-title":"Cryptography and Coding","author":"U.M. Maurer","year":"2005","unstructured":"Maurer, U.M.: Abstract models of computation in cryptography. In: Smart, N.P. (ed.) Cryptography and Coding. LNCS, vol.\u00a03796, pp. 1\u201312. Springer, Heidelberg (2005)"},{"key":"62_CR6","first-page":"222","volume-title":"Proc. 18th FOCS, IEEE 1977","author":"A.C.C. Yao","year":"1977","unstructured":"Yao, A.C.C.: Probabilistic computations: towards a unified measure of complexity. In: Proc. 18th FOCS, IEEE 1977, pp. 222\u2013227. IEEE Computer Society Press, Los Alamitos (1977)"},{"key":"62_CR7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"62_CR8","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0304-3975(85)90210-5","volume":"38","author":"M. Snir","year":"1985","unstructured":"Snir, M.: Lower bounds on probabilistic linear decision trees. Theoret. Comput. Sci.\u00a038, 69\u201382 (1985)","journal-title":"Theoret. Comput. Sci."},{"key":"62_CR9","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/BF01270387","volume":"6","author":"D. Grigoriev","year":"1997","unstructured":"Grigoriev, D., Karpinski, M., Meyer auf der Heide, F.: A lower bound for randomized algebraic decision trees. Comput. Complexity\u00a06, 357\u2013375 (1996\/1997)","journal-title":"Comput. Complexity"},{"key":"62_CR10","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1145\/800070.802197","volume-title":"STOC 1982: Proceedings of the fourteenth annual ACM symposium on Theory of computing","author":"U. Manber","year":"1982","unstructured":"Manber, U., Tompa, M.: Probabilistic, nondeterministic, and alternating decision trees (preliminary version). In: STOC 1982: Proceedings of the fourteenth annual ACM symposium on Theory of computing, New York, NY, USA, pp. 234\u2013244. ACM Press, New York (1982)"},{"key":"62_CR11","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1145\/3828.3838","volume":"32","author":"U. Manber","year":"1985","unstructured":"Manber, U., Tompa, M.: The complexity of problems on probabilistic, nondeterministic, and alternating decision trees. J. Assoc. Comput. Mach.\u00a032, 720\u2013732 (1985)","journal-title":"J. Assoc. Comput. Mach."},{"key":"62_CR12","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1137\/0213008","volume":"13","author":"U. Manber","year":"1984","unstructured":"Manber, U., Tompa, M.: The effect of number of Hamiltonian paths on the complexity of a vertex-coloring problem. SIAM J. Comput.\u00a013, 109\u2013115 (1984)","journal-title":"SIAM J. Comput."},{"key":"62_CR13","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0167-5060(08)70060-8","volume":"9","author":"M. Chein","year":"1980","unstructured":"Chein, M., Habib, M.: The jump number of DAGs and posets: An introduction. Annals of Discrete Mathematics\u00a09, 189\u2013194 (1980)","journal-title":"Annals of Discrete Mathematics"},{"key":"62_CR14","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"Blum, M., Floyd, R., Pratt, V., Rivest, R., Tarjan, R.: Time bounds for selection. Journal of Computer and System Sciences\u00a07, 448\u2013461 (1973)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74456-6_62.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:29:35Z","timestamp":1619504975000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74456-6_62"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540744559","9783540744566"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74456-6_62","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}