{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:09:54Z","timestamp":1725664194401},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540600848"},{"type":"electronic","value":"9783540494256"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60084-1_73","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:38:04Z","timestamp":1330277884000},"page":"183-195","source":"Crossref","is-referenced-by-count":3,"title":["Lower time bounds for randomized computation"],"prefix":"10.1007","author":[{"given":"R\u016asi\u0146\u0161","family":"Freivalds","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Karpinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"16_CR1","first-page":"201","volume":"233","author":"R. Freivalds","year":"1975","unstructured":"Freivalds, R., Fast computations by probabilistic Turing machines, Proceedings of Latvian State University, 233(1975), pp. 201\u2013205 (Russian)","journal-title":"Proceedings of Latvian State University"},{"key":"16_CR2","unstructured":"Freivalds, R., Probabilistic machines can use Isess runnning time, Information Processing'77 (Proc. IFIP Congress'77), North Holland, 1977, pp. 839\u2013842"},{"key":"16_CR3","first-page":"209","volume":"36","author":"R. Freivalds","year":"1979","unstructured":"Freivalds, R., Speeding up recognition of some sets by usage of random number generators, Problemi kibernetiki, 36(1979), pp. 209\u2013224 (Russian)","journal-title":"Problemi kibernetiki"},{"key":"16_CR4","first-page":"33","volume":"118","author":"R. Freivalds","year":"1981","unstructured":"Freivalds, R., Probabilistic two-way machines, LNCS, 118(1981), pp.33\u201345","journal-title":"LNCS"},{"key":"16_CR5","first-page":"159","volume":"158","author":"R. Freivalds","year":"1983","unstructured":"Freivalds, R., Space and reversal complexity of probabilistic one-way Turing machines, LNCS, 158(1983), pp. 159\u2013170","journal-title":"LNCS"},{"key":"16_CR6","first-page":"39","volume":"24","author":"R. Freivalds","year":"1985","unstructured":"Freivalds, R., Space and reversal complexity of probabilistic one-way Turing machines, Annals of Discrete Mathematics, 24(1985), pp. 39\u201350","journal-title":"Annals of Discrete Mathematics"},{"issue":"177","key":"16_CR7","first-page":"108","volume":"No.2","author":"R. Freivalds","year":"1977","unstructured":"Freivalds, R., Ikaunieks, E., On advantages of nondeterministic machines over probabilistic ones, Izvestiya VUZ. Matematika, No.2(177), 1977, pp.108\u2013123 (Russian)","journal-title":"Izvestiya VUZ. Matematika"},{"key":"16_CR8","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1007\/3-540-58201-0_100","volume":"820","author":"R. Freivalds","year":"1994","unstructured":"Freivalds, R., Karpinski, M., Lower space bounds for randomized computation, Lecture Notes in Computer Science, vol. 820(1994), pp. 580\u2013592","journal-title":"Lecture Notes in Computer Science"},{"key":"16_CR9","volume-title":"Information Theory and Reliable Communication","author":"R.G. Gallager","year":"1968","unstructured":"Gallager, R.G., Information Theory and Reliable Communication. John Wiley, NY, 1968"},{"key":"16_CR10","doi-asserted-by":"crossref","first-page":"840","DOI":"10.1137\/0213052","volume":"13","author":"J. Ja'Ja'","year":"1984","unstructured":"Ja'Ja', J., Prasanna Kumar, V.K., Simon, J., Information transfer under different sets of protocols, SIAM J. Computation, 13(1984), pp.840\u2013849","journal-title":"SIAM J. Computation"},{"key":"16_CR11","first-page":"355","volume":"452","author":"J. Kaneps","year":"1990","unstructured":"Kaneps, J. and Freivalds R., Minimal nontrivial space complexity of probabilistic one-way Turing machines, LNCS, 452(1990), pp. 355\u2013361","journal-title":"LNCS"},{"key":"16_CR12","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/0890-5401(87)90057-5","volume":"75","author":"M. Karpinski","year":"1987","unstructured":"Karpinski, M. and Verbeek, R., On the Monte Carlo space constructible functions and space separation results for probabilistic complexity classes, Information and Computation, 75(1987), pp. 178\u2013189","journal-title":"Information and Computation"},{"key":"16_CR13","first-page":"189","volume":"270","author":"M. Karpinski","year":"1988","unstructured":"Karpinski, M. and Verbeek, R., Randomness, probability, and the separation of Monte Carlo time and space, LNCS, 270(1988), pp. 189\u2013207","journal-title":"LNCS"},{"key":"16_CR14","first-page":"227","volume":"700","author":"M. Karpinski","year":"1993","unstructured":"Karpinski, M. and Verbeek, R., On randomized versus deterministic computation, Proc. ICALP'93, LNCS, 700(1993), pp. 227\u2013240","journal-title":"Proc. ICALP'93, LNCS"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Ming Li, Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer, 1993","DOI":"10.1007\/978-1-4757-3860-5"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"Stearns, R.E., Hartmanis, J., Lewis, P.M., Hiearchies of memory limited computations, Proc. IEEE Conference on Switch., Circuit Theory and Logical Design, 1965, pp. 179\u2013190","DOI":"10.1109\/FOCS.1965.11"}],"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-60084-1_73.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:54:41Z","timestamp":1605646481000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60084-1_73"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540600848","9783540494256"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-60084-1_73","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}