{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T15:47:32Z","timestamp":1742917652158,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662480533"},{"type":"electronic","value":"9783662480540"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48054-0_38","type":"book-chapter","created":{"date-parts":[[2015,8,10]],"date-time":"2015-08-10T11:57:29Z","timestamp":1439207849000},"page":"459-471","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape"],"prefix":"10.1007","author":[{"given":"Debasis","family":"Mandal","sequence":"first","affiliation":[]},{"given":"A.","family":"Pavan","sequence":"additional","affiliation":[]},{"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,8,11]]},"reference":[{"key":"38_CR1","doi-asserted-by":"crossref","unstructured":"Adleman, L.M.: Two theorems on random polynomial time. In: Proceedings of the 19th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 75\u201383 (1978)","DOI":"10.1109\/SFCS.1978.37"},{"key":"38_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"issue":"1\u20133","key":"38_CR3","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0019-9958(83)80060-6","volume":"58","author":"A Borodin","year":"1983","unstructured":"Borodin, A., Cook, S., Pippenger, N.: Parallel computation for well-endowed rings and space-bounded probabilistic machines. Inf. Control 58(1\u20133), 113\u2013136 (1983)","journal-title":"Inf. Control"},{"issue":"3","key":"38_CR4","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/1978782.1978785","volume":"7","author":"KM Chung","year":"2011","unstructured":"Chung, K.M., Reingold, O., Vadhan, S.: S-T connectivity on digraphs with a known stationary distribution. ACM Trans. Algorithms 7(3), 30 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"38_CR5","unstructured":"David, M., Nguyen, P., Papakonstantinou, P.A., Sidiropoulos, A.: Computationally Limited Randomness. In: Proceedings of the Innovations in Theoretical Computer Science (ITCS) (2011)"},{"issue":"16","key":"38_CR6","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1016\/j.ipl.2011.04.013","volume":"111","author":"M David","year":"2011","unstructured":"David, M., Papakonstantinou, P.A., Sidiropoulos, A.: How strong is Nisan\u2019s pseudo-random generator? Inf. Process. Lett. 111(16), 804\u2013808 (2011)","journal-title":"Inf. Process. Lett."},{"key":"38_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/11672142_38","volume-title":"STACS 2006","author":"L Fortnow","year":"2006","unstructured":"Fortnow, L., Klivans, A.R.: Linear advice for randomized logarithmic space. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 469\u2013476. Springer, Heidelberg (2006)"},{"issue":"4","key":"38_CR8","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J Gill","year":"1977","unstructured":"Gill, J.: Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6(4), 675\u2013695 (1977)","journal-title":"SIAM J. Comput."},{"key":"38_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/978-3-540-27821-4_34","volume-title":"approximation, randomization, and combinatorial optimization. algorithms and techniques","author":"D Gutfreund","year":"2004","unstructured":"Gutfreund, D., Viola, E.: Fooling parity tests with parity gates. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol. 3122, pp. 381\u2013392. Springer, Heidelberg (2004)"},{"issue":"2","key":"38_CR10","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1145\/322003.322015","volume":"24","author":"JH Hopcroft","year":"1977","unstructured":"Hopcroft, J.H., Paul, W.J., Valiant, L.G.: On Time Versus Space. J. ACM 24(2), 332\u2013337 (1977)","journal-title":"J. ACM"},{"key":"38_CR11","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Nisan, N., Wigderson, A.: Pseudorandomness for network algorithms. In: Proceedings of the 26th ACM Symposium on Theory of Computing (STOC), pp. 356\u2013364 (1994)","DOI":"10.1145\/195058.195190"},{"key":"38_CR12","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0304-3975(02)00830-7","volume":"302","author":"G Karakostas","year":"2003","unstructured":"Karakostas, G., Lipton, R.J., Viglas, A.: On the complexity of intersecting finite state automata and NL versus NP. Theor. Comput. Sci. 302, 257\u2013274 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"1985","key":"38_CR13","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/S0019-9958(85)80032-2","volume":"67","author":"M Karpinski","year":"1985","unstructured":"Karpinski, M., Verbeek, R.: There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator. Inf. Control 67(1985), 158\u2013162 (1985)","journal-title":"Inf. Control"},{"key":"38_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-540-45077-1_29","volume-title":"Fundamentals of Computation Theory","author":"RJ Lipton","year":"2003","unstructured":"Lipton, R.J., Viglas, A.: Non-uniform depth of polynomial time and space simulations. In: Lingas, A., Nilsson, B.J. (eds.) FCT 2003. LNCS, vol. 2751, pp. 311\u2013320. Springer, Heidelberg (2003)"},{"issue":"4","key":"38_CR15","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/BF01305237","volume":"12","author":"N Nisan","year":"1992","unstructured":"Nisan, N.: Pseudorandom generators for space-bounded computation. Combinatorica 12(4), 449\u2013461 (1992)","journal-title":"Combinatorica"},{"issue":"1","key":"38_CR16","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0304-3975(93)90258-U","volume":"107","author":"N Nisan","year":"1993","unstructured":"Nisan, N.: On read once vs. multiple access to randomness in logspace. Theor. Comput. Sci. 107(1), 135\u2013144 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"38_CR17","doi-asserted-by":"crossref","unstructured":"Raz, R., Reingold, O.: On recycling the randomness of states in space bounded computation. In: Proceedings of the 31st ACM Symposium on Theory of Computing (STOC), pp. 159\u2013168 (1999)","DOI":"10.1145\/301250.301294"},{"issue":"4","key":"38_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 1\u201324 (2008)","journal-title":"J. ACM"},{"key":"38_CR19","doi-asserted-by":"crossref","unstructured":"Reingold, O., Trevisan, L., Vadhan, S.: Pseudorandom walks on regular digraphs and the $${\\rm RL}$$ vs. $${\\rm L}$$ problem. In: Proceedings of the 38th ACM Symposium on Theory of Computing (STOC), p. 457 (2006)","DOI":"10.1145\/1132516.1132583"},{"key":"38_CR20","unstructured":"Saks, M.: Randomization and derandomization in space-bounded computation. In: Proceedings of the 11th IEEE Conference on Computational Complexity (1996)"},{"key":"38_CR21","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1006\/jcss.1998.1616","volume":"403","author":"M Saks","year":"1999","unstructured":"Saks, M., Zhou, S.: $${\\rm BPSPACE}(S) \\subseteq {\\rm DSPACE}(S^{3\/2})$$. J. Comput. Syst. Sci. 403, 376\u2013403 (1999)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"38_CR22","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1137\/S0097539703438629","volume":"35","author":"R Santhanam","year":"2005","unstructured":"Santhanam, R., van Melkebeek, D.: Holographic proofs and derandomization. SIAM J. Comput. 35(1), 59\u201390 (2005)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2015"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48054-0_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T06:15:08Z","timestamp":1676960108000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-48054-0_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662480533","9783662480540"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48054-0_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"11 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}