{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T00:56:18Z","timestamp":1778547378443,"version":"3.51.4"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,9,1]],"date-time":"2008-09-01T00:00:00Z","timestamp":1220227200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2.00E+13"],"award-info":[{"award-number":["2.00E+13"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2008,9]]},"abstract":"<jats:p>\n            We present a\n            <jats:italic>deterministic<\/jats:italic>\n            , log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log\n            <jats:sup>4\/3<\/jats:sup>\n            (\u22c5) obtained by Armoni, Ta-Shma, Wigderson and Zhou (JACM 2000). As undirected st-connectivity is complete for the class of problems solvable by symmetric, nondeterministic, log-space computations (the class SL), this algorithm implies that SL = L (where L is the class of problems solvable by deterministic log-space computations). Independent of our work (and using different techniques), Trifonov (STOC 2005) has presented an\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            log log\n            <jats:italic>n<\/jats:italic>\n            )-space, deterministic algorithm for undirected st-connectivity.\n          <\/jats:p>\n          <jats:p>\n            Our algorithm also implies a way to construct in log-space a\n            <jats:italic>fixed<\/jats:italic>\n            sequence of directions that guides a deterministic walk through all of the vertices of any connected graph. Specifically, we give log-space constructible universal-traversal sequences for graphs with restricted labeling and log-space constructible universal-exploration sequences for general graphs.\n          <\/jats:p>","DOI":"10.1145\/1391289.1391291","type":"journal-article","created":{"date-parts":[[2008,9,16]],"date-time":"2008-09-16T16:32:40Z","timestamp":1221582760000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":324,"title":["Undirected connectivity in log-space"],"prefix":"10.1145","volume":"55","author":[{"given":"Omer","family":"Reingold","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science Rehovot, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,9,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28410"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.34"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90014-9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050203"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548399004071"},{"key":"e_1_2_1_8_1","first-page":"039","article-title":"A compendium of problems complete for symmetric logarithmic space","volume":"3","author":"Alvarez C.","year":"1996","unstructured":"Alvarez , C. , and Greenlaw , R. 1996 . A compendium of problems complete for symmetric logarithmic space . Electronic Colloquium on Computational Complexity (ECCC) 3 , 039 . Alvarez, C., and Greenlaw, R. 1996. A compendium of problems complete for symmetric logarithmic space. Electronic Colloquium on Computational Complexity (ECCC) 3, 039.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/333979.333984"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100242"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1122"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218038"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.45"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.30"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275669"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73063"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90040-4"},{"key":"e_1_2_1_19_1","unstructured":"Goldreich O. 2005. Bravely moderately: A common theme in four recent results. Electronic Colloquium on Computational Complexity (ECCC) 098. (Also appeared as part of SIGACT news complexity theory column 51.)  Goldreich O. 2005. Bravely moderately: A common theme in four recent results. Electronic Colloquium on Computational Complexity (ECCC) 098. (Also appeared as part of SIGACT news complexity theory column 51.)"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804106"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 6th International Workshop on Randomization and Computation (RANDOM). 209--223","author":"Goldreich O.","unstructured":"Goldreich , O. , and Wigderson , A . 2002. Derandomization that is rarely wrong from short advice that is typically good . In Proceedings of the 6th International Workshop on Randomization and Computation (RANDOM). 209--223 . Goldreich, O., and Wigderson, A. 2002. Derandomization that is rarely wrong from short advice that is typically good. In Proceedings of the 6th International Workshop on Randomization and Computation (RANDOM). 209--223."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90199-J"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195190"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579322"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 8th Structures in Complexity conference. 102--111","author":"Karchmer M.","unstructured":"Karchmer , M. , and Wigderson , A . 1993. On span programs . In Proceedings of the 8th Structures in Complexity conference. 102--111 . Karchmer, M., and Wigderson, A. 1993. On span programs. In Proceedings of the 8th Structures in Complexity conference. 102--111."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700389652"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the IEEE Conference on Computational Complexity (CCC). IEEE Computer Society Press","author":"Koucky M.","year":"2001","unstructured":"Koucky , M. 2001 . Universal traversal sequences with backtracking . In Proceedings of the IEEE Conference on Computational Complexity (CCC). IEEE Computer Society Press , Los Alamitos, CA, 21--27. Koucky, M. 2001. Universal traversal sequences with backtracking. In Proceedings of the IEEE Conference on Computational Complexity (CCC). IEEE Computer Society Press, Los Alamitos, CA, 21--27."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90058-5"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Madras N.","unstructured":"Madras , N. , and Randall , D . 1996. Factoring Markov chains to bound mixing rates . In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press , Los Alamitos, CA, 194--203. Madras, N., and Randall, D. 1996. Factoring Markov chains to bound mixing rates. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 194--203."},{"key":"e_1_2_1_33_1","first-page":"71","article-title":"Explicit constructions of expanders","volume":"9","author":"Margulis G. A.","year":"1973","unstructured":"Margulis , G. A. 1973 . Explicit constructions of expanders . Problemy Peredachi Informatsii 9 , 4, 71 -- 80 . Margulis, G. A. 1973. Explicit constructions of expanders. Problemy Peredachi Informatsii 9, 4, 71--80.","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_2_1_34_1","first-page":"51","article-title":"Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators","volume":"24","author":"Margulis G. A.","year":"1988","unstructured":"Margulis , G. A. 1988 . Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators . Problemy Peredachi Informatsii 24 , 1, 51 -- 60 . Margulis, G. A. 1988. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii 24, 1, 51--60.","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796563"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1054"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305237"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129772"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267822"},{"key":"e_1_2_1_40_1","article-title":"Symmetric logspace is closed under complement. Chicago","author":"Nisan N.","year":"1995","unstructured":"Nisan , N. , and Ta-Shma , A. 1995 . Symmetric logspace is closed under complement. Chicago J. Theor. Comput. Sci. Nisan, N., and Ta-Shma, A. 1995. Symmetric logspace is closed under complement. Chicago J. Theor. Comput. Sci.","journal-title":"J. Theor. Comput. Sci."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0004"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 7th Annual Teletraffic Conference","author":"Pinsker M. S.","year":"1973","unstructured":"Pinsker , M. S. 1973 . On the complexity of a concentrator . In Proceedings of the 7th Annual Teletraffic Conference . Stockholm, 318\/1--318\/4. Pinsker, M. S. 1973. On the complexity of a concentrator. In Proceedings of the 7th Annual Teletraffic Conference. Stockholm, 318\/1--318\/4."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301294"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/62.322436"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132583"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796583"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796583"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_37"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/791229.792257"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1616"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/0605030"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060684"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/645721.666377"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1391289.1391291","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1391289.1391291","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:58:04Z","timestamp":1750255084000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1391289.1391291"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,9]]},"references-count":53,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,9]]}},"alternative-id":["10.1145\/1391289.1391291"],"URL":"https:\/\/doi.org\/10.1145\/1391289.1391291","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,9]]},"assertion":[{"value":"2008-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-09-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}