{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T05:21:39Z","timestamp":1740374499443,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540206804"},{"type":"electronic","value":"9783540245971"}],"license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-24597-1_18","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T07:39:20Z","timestamp":1280389160000},"page":"208-216","source":"Crossref","is-referenced-by-count":2,"title":["Randomized Time-Space Tradeoffs for Directed Graph Connectivity"],"prefix":"10.1007","author":[{"given":"Parikshit","family":"Gopalan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard J.","family":"Lipton","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aranyak","family":"Mehta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Aleliunas, R., Karp, R., Lipton, R., Lovasz, L., Rakoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: 20th Annual Symposium on Foundations of Computer Science, pp. 218\u2013223 (1979)","DOI":"10.1109\/SFCS.1979.34"},{"key":"18_CR2","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1145\/333979.333984","volume":"47","author":"R. Armoni","year":"2000","unstructured":"Armoni, R., Ta-Shma, A., Wigderson, A., Zhou, S.: An log(n)4\/3 space algorithm for s-t connectivity in undirected graphs. Journal of the ACM\u00a047, 294\u2013311 (2000)","journal-title":"Journal of the ACM"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Barnes, G., Buss, J., Ruzzo, W., Schieber, B.: A sub-linear space, polynomial time algorithm for directed s-t connectivity. In: 7th annual conference on Structure in Complexity Theory, pp. 27\u201333 (1992)","DOI":"10.1109\/SCT.1992.215378"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Berman, P., Simon, J.: Lower bounds on graph threading by probabilistic machines. In: 24th Annual Symposium on Foundations of Computer Science, pp. 304\u2013311 (1983)","DOI":"10.1109\/SFCS.1983.31"},{"issue":"3","key":"18_CR5","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1137\/0209048","volume":"9","author":"S. Cook","year":"1980","unstructured":"Cook, S., Rackoff, C.: Space lower bounds for maze threadability on restricted machines. SIAM Journal on Computing\u00a09(3), 636\u2013652 (1980)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"18_CR6","doi-asserted-by":"publisher","first-page":"2257","DOI":"10.1137\/S0097539795295948","volume":"28","author":"J. Edmonds","year":"1999","unstructured":"Edmonds, J., Poon, C., Achlioptas, D.: Tight lower bounds for st-connectivity on the NNJAG model. SIAM J. Comput.\u00a028(6), 2257\u20132284 (1999)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"18_CR7","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1006\/jcss.1997.1471","volume":"54","author":"U. Feige","year":"1997","unstructured":"Feige, U.: A spectrum of time-space tradeoffs for undirected s-t connectivity. Journal of Computer and System Sciences\u00a054(2), 305\u2013316 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Gill, J.: Computational complexity of probabilistic turing machines. In: Proc. 6th Annual ACM Symp. Theory of Computing, pp. 91\u201395 (1974)","DOI":"10.1145\/800119.803889"},{"key":"18_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01205052","volume":"4","author":"N. Nisan","year":"1994","unstructured":"Nisan, N.: RL \u2282 SC. Journal of Computational Complexity\u00a04, 1\u201311 (1994)","journal-title":"Journal of Computational Complexity"},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Nisan, N., Szemeredi, E., Wigderson, A.: Undirected connectivity in O(log1.5n) space. In: Proceedings of the 30th FOCS, pp. 24\u201329 (1989)","DOI":"10.1109\/SFCS.1992.267822"},{"key":"18_CR11","unstructured":"Poon, C.: Personal communication"},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"Poon, C.: Space bounds for graph connectivity problems on node named jags and node ordered jags. In: 34th Annual Symposium on Foundations of Computer Science, pp. 218\u2013227 (1993)","DOI":"10.1109\/SFCS.1993.366865"},{"key":"18_CR13","unstructured":"Poon, C.: On the complexity of the s-t connectivity problem. Ph.D Thesis, University of Toronto (1996)"},{"issue":"2","key":"18_CR14","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. Savitch","year":"1970","unstructured":"Savitch, W.: Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences\u00a04(2), 177\u2013192 (1970)","journal-title":"Journal of Computer and System Sciences"},{"key":"18_CR15","unstructured":"Saks, M.: Randomization and derandomization in space-bounded computation. In: Annual Conference on Structure in Complexity Theory (1996)"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"Simon, J.: Space-bounded probabilistic turing machine complexity classes are closed under complement. In: Proc. 13th Annual ACM Symp. Theory of Computing, pp. 158\u2013167 (1981)","DOI":"10.1145\/800076.802469"},{"key":"18_CR17","doi-asserted-by":"crossref","unstructured":"Wigderson, A.: The complexity of graph connectivity. In: Proceedings of the 17th Mathematical Foundations of Computer Science, pp. 112\u2013132 (1992)","DOI":"10.1007\/3-540-55808-X_10"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24597-1_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T15:21:12Z","timestamp":1740324072000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24597-1_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540206804","9783540245971"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24597-1_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}