{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:24Z","timestamp":1787337504507,"version":"build-2736575974"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>Undirected st-connectivity is an important problem in computing. There are algorithms for this problem that use O(n) time and ones that use O(log n) space. The main result of this paper is that, in a very natural structured model, these upper bounds are not simultaneously achievable. Any probabilistic jumping automaton for graphs (JAG) requires either space $\\Omega( \\log^2 n \/ \\log log n )$ or time $n^{(1 + \\Omega ( 1 \/ \\log \\log n )) }$ to solve undirected st-connectivity.<\/jats:p>","DOI":"10.1137\/s0097539794277135","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1492-1513","source":"Crossref","is-referenced-by-count":1,"title":["Time--Space Tradeoffs For Undirected st-Connectivity on a Graph Automata"],"prefix":"10.1137","volume":"27","author":[{"given":"Jeff A.","family":"Edmonds","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"Romas Aleliunas, Richard Karp, Richard Lipton, L\u00e1szl\u00f3 Lov\u00e1sz, Charles Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, IEEE, New York, 1979, 218\u201322382h:68084"},{"key":"R2","unstructured":"G. Barnes and U. Feige,\n                      Short random walks on graphs\n                      , in Proc. 25th Annual ACM Symposium on Theory of Computing, San Diego, CA, May 1993, pp. 728\u2013737."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793283151"},{"key":"R4","unstructured":"G. Barnes and J. Edmonds,\n                      Time\u2010space lower bounds for directed st\u2010connectivity on JAG models\n                      , in Proc. 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, November 1993, pp. 228\u2013237."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0085"},{"key":"R6","unstructured":"P. Berman and J. Simon,\n                      Lower bounds on graph threading by probabilistic machines\n                      , in Proc. 24th Annual Symposium on Foundations of Computer Science, IEEE, Tucson, AZ, November 1983, pp. 304\u2013311."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90046-L"},{"key":"R8","unstructured":"A. Borodin,\n                      Structured vs. general models in computational complexity\n                      , L\u2019Enseignement Math\u00e9matique, 28 (1982)."},{"key":"R9","unstructured":"A. Z. Broder, A. R. Karlin, P. Raghavan, and E. Upfal,\n                      Trading space for time in undirected s\u2010t connectivity\n                      , in Proc. 21st Annual ACM Symposium on Theory of Computing, Seattle, WA, May 1989, pp. 543\u2013549."},{"key":"R10","unstructured":"A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensky, and P. Tiwari,\n                      The electrical resistance of a graph captures its commute and cover times\n                      , in Proc. 21st Annual ACM Symposium on Theory of Computing, Seattle, WA, May 1989, pp. 574\u2013586."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0209048"},{"key":"R12","unstructured":"J. Edmonds,\n                      Time\u2010Space Lower Bounds for Undirected and Directed ST\u2010Connectivity on JAG Models\n                      , Ph.D. thesis, Department of Computer Science, University of Toronto, August 1993."},{"key":"R13","unstructured":"J. Edmonds,\n                      Time\u2010space trade\u2010offs for undirected st\u2010connectivity on a JAG\n                      , in Proc. 25th Annual ACM Symposium on Theory of Computing, San Diego, CA, May 1993, pp. 718\u2013727."},{"key":"R14","unstructured":"R. Impagliazzo and D. Zuckerman,\n                      How to recycle random bits\n                      , in Proc. 30th Annual Symposium on Foundations of Computer Science, IEEE, Research Triangle Park, NC, October 1989, pp. 248\u2013253."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01048274"},{"key":"R16","unstructured":"Logic and Algorithmic\n                      , an International Symposium Held in Honor of Ernst Specker, Z\u00fcrich, February 5\u201311, 1980."},{"key":"R16","unstructured":"Monographie 30 de L\u2019Enseignement Math\u00e9matique, Universit\u00e9 de Gen\u00e8ve, 1982."},{"key":"R17","unstructured":"N. Nisan, E. Szemer\u00e9di, and A. Wigderson,\n                      Undirected connectivity in O(log1.5n) space\n                      , in Proc. 33rd Annual Symposium on Foundations of Computer Science, IEEE, Pittsburgh, PA, October 1992, pp. 24\u201329."},{"key":"R18","unstructured":"C. K. Poon,\n                      A Sublinear Space, Polynomial Time Algorithm for Directed ST\u2010Connectivity on the JAG Model\n                      , Ph.D. thesis, University of Toronto, 1995."},{"key":"R19","unstructured":"S. Rudich, personal communication, 1994."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80031-5"},{"key":"R22","unstructured":"N. A. Spencer, John Wiley and Sons, Inc., 1992."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"R24","unstructured":"Avi Wigderson, The complexity of graph connectivity, Lecture Notes in Comput. Sci., Vol. 629, Springer, Berlin, 1992, 112\u201313294j:05130"},{"key":"R25","unstructured":"A. C. Yao,\n                      Probabilistic computations: Toward a unified measure of complexity\n                      , in Proc. 18th Annual Symposium on Foundations of Computer Science, IEEE, Providence, RI, October 1977, pp. 222\u2013227."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794277135","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:23Z","timestamp":1787336063000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794277135"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794277135"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794277135","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}