{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:14:42Z","timestamp":1763468082258,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":54,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540558088"},{"type":"electronic","value":"9783540472919"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55808-x_10","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T09:45:00Z","timestamp":1330249500000},"page":"112-132","source":"Crossref","is-referenced-by-count":24,"title":["The complexity of graph connectivity"],"prefix":"10.1007","author":[{"given":"Avi","family":"Wigderson","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,7,30]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, On the complexity of the pigeonhole principle, Proc. of the 29th FOCS, pp. 346\u2013355, 1988.","DOI":"10.1109\/SFCS.1988.21951"},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/0168-0072(89)90036-5","volume":"45","author":"M. Ajtai","year":"1989","unstructured":"M. Ajtai, First-order definability on finite structures, Annals of Pure and Applied Logic, 45, pp. 211\u2013225, 1989.","journal-title":"Annals of Pure and Applied Logic"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"M. Ajtai and M. Ben-Or, A theorem on probabilistic constant-depth computation, Proc. of the 16th STOC, pp. 471\u2013474, 1984.","DOI":"10.1145\/800057.808715"},{"issue":"No1","key":"10_CR4","doi-asserted-by":"publisher","first-page":"113","DOI":"10.2307\/2274958","volume":"55","author":"M. Ajtai","year":"1990","unstructured":"M. Ajtai and R. Fagin, Reachability is harder for directed than for undirected finite graphs, The journal of Symbolic Logic, Vol 55, No 1, pp. 113\u2013150, 1990.","journal-title":"The journal of Symbolic Logic"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Komlos, E. Szemeredi, Deterministic simulation in logspace, Proc. of the 19th STOC, pp. 132\u2013140, 1987.","DOI":"10.1145\/28395.28410"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovasz, C. Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, Proc. of the 20th FOCS, pp. 218\u2013223, 1979.","DOI":"10.1109\/SFCS.1979.34"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"P. Berman and J. Simon, Lower bounds for graph threading by probabilistic machines, Proc. of the 24th FOCS, pp. 304\u2013311, 1983.","DOI":"10.1109\/SFCS.1983.31"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"B. Bollobas, Extremal Graph Theory, Academic Press, 1978.","DOI":"10.1007\/978-1-4612-9967-7"},{"key":"10_CR9","unstructured":"G. Barnes, J. F. Buss, W. L. Ruzzo and B. Schieber, A sublinear space, polynomial time algorithm for directed s-t connectivity, Technical report 92-03-05, Dept. of Computer Science, University of Washington, 1992."},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1137\/0218038","volume":"18","author":"A. Borodin","year":"1989","unstructured":"A. Borodin, S. A. Cook, P. W. Dymond, W. L. Ruzzo and M. Tompa, Two applications of inductive counting for complementation problems, SIAM J. on Computing, Vol 18, pp. 559\u2013578, 1989.","journal-title":"SIAM J. on Computing"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"P. Beame, R. Impagliazzo, J. Krajicek, T. Pitassi, P. Pudlak and A. Woods, Exponential lower bounds for the pigeonhole principle, Proc. of the 24th STOC, pp. 200\u2013220.","DOI":"10.1145\/129712.129733"},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"4","author":"M. Blum","year":"1984","unstructured":"M. Blum and S. Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM J. on Computing, 13, 4, pp. 850\u2013864, 1984.","journal-title":"SIAM J. on Computing, 13"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"L. Babai, N. Nisan and M. Szegedy, Multi-party protocols and logspacehard pseudo-random sequences, Proc. of the 21st STOC, pp.1\u201311, 1989.","DOI":"10.1145\/73007.73008"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"G. Barnes and W. L. Ruzzo, Deterministic algorithms for undirected st-connectivity using polynomial time and sublinear space, Proc. 23rd STOC, pp. 43\u201353, 1991.","DOI":"10.1145\/103418.103430"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"R. Boppana and M. Sipser, The complexity of finite functions, Handbook of Theoretical Compluter Science, Vol. A, van Leeuwen (ed.), MIT Press\/Elsvier, pp. 759\u2013804, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"issue":"2","key":"10_CR16","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"L. Carter","year":"1979","unstructured":"L. Carter and M. Wegman, Universal hash functions, J. of Computer Systems and Sciences, 18, 2, pp. 143\u2013154, 1979.","journal-title":"J. of Computer Systems and Sciences"},{"key":"10_CR17","first-page":"2","volume":"64","author":"S. A. Cook","year":"1985","unstructured":"S. A. Cook, A taxonomy of problems with fast parallel algorithms, Information and Computation, 64, pp. 2\u201322, 1985.","journal-title":"Information and Computation"},{"key":"10_CR18","doi-asserted-by":"crossref","unstructured":"A. Cohen and A. Wigderson, Dispersers, deterministic amplification and weak random sources, Proc. of the 30th FOCS, pp. 14\u201319, 1989.","DOI":"10.1109\/SFCS.1989.63449"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, Proc. of the 19th STOC, pp. 1\u20136, 1987.","DOI":"10.1145\/28395.28396"},{"key":"10_CR20","doi-asserted-by":"crossref","unstructured":"A. Chandra, M. Furst and R. J. Lipton, Multi-party protocols, Proc. of the 15th STOC, pp. 94\u201399, 1983.","DOI":"10.1145\/800061.808737"},{"issue":"No2","key":"10_CR21","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0890-5401(91)90065-A","volume":"91","author":"M. Chrobak","year":"1991","unstructured":"M. Chrobak, H. Karloff, T. Radzik, Connectivity vs. reachability, Information and Computation, Vol 91, No 2, pp. 177\u2013188, 1991.","journal-title":"Information and Computation"},{"key":"10_CR22","unstructured":"S. Cook and P. McKenzie, manuscript, 1986."},{"issue":"No3","key":"10_CR23","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1137\/0209048","volume":"9","author":"S. A. Cook","year":"1980","unstructured":"Springer-VerlagS. A. Cook and C. W. Rackoff, Space lower bounds for maze threadability on restricted machines, SIAM J. on Computing, Vol 9, No 3, pp. 636\u2013652, 1980.","journal-title":"SIAM J. on Computing"},{"key":"10_CR24","unstructured":"H. B. Enderton, A Mathematical Introduction to Logic, Academic Press, 1972."},{"key":"10_CR25","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4064\/fm-49-2-129-141","volume":"49","author":"A. Ehrenfeucht","year":"1961","unstructured":"A. Ehrenfeucht, An application of games to the completeness problem for formalized theories, Fund. Math., 49, pp. 129\u2013141, 1961.","journal-title":"Fund. Math."},{"key":"10_CR26","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1002\/malq.19750210112","volume":"21","author":"R. Fagin","year":"1975","unstructured":"R. Fagin, Monadic generalized spectra, Seitschrift fur Mathematische Logik und Grundlagen der Mathematik, Vol 21, pp. 89\u201396, 1975.","journal-title":"Seitschrift fur Mathematische Logik und Grundlagen der Mathematik"},{"key":"10_CR27","first-page":"35","volume":"1","author":"R. Fraisse","year":"1954","unstructured":"R. Fraisse, Sur les classifications des systems de relations, Publications Scientifiques de l'Universit\u00e9 d'Alger, Vol 1. pp. 35\u2013182, 1954.","journal-title":"Publications Scientifiques de l'Universit\u00e9 d'Alger"},{"key":"10_CR28","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. Saxe and M. Sipser, Parity, circuits and the polynomial-time hierarchy, Math System Theory 17, pp. 13\u201327, 1984.","journal-title":"Math System Theory"},{"key":"10_CR29","unstructured":"M. Grigni and M. Sipser, Monotone complexity, Proceedings of LMS workshop on Boolean function complexity, Durham, M. Paterson (Ed.), Cambridge University Press, 1990."},{"key":"10_CR30","doi-asserted-by":"crossref","unstructured":"M. Grigni and M. Sipser, Monotone separation of Logspace from NC 1, Proc. of the 6th Structures in Complexity Theory conference, pp. 294\u2013298, 1991.","DOI":"10.1109\/SCT.1991.160272"},{"key":"10_CR31","unstructured":"J. Hastad, Computational limitations of small-depth circuits, The MIT Press, 1987."},{"key":"10_CR32","doi-asserted-by":"crossref","unstructured":"S. Istrail, Polynomial traversing sequences for cycles are constructible, Proc. of the 20th STOC, pp. 491\u2013503, 1988.","DOI":"10.1145\/62212.62260"},{"key":"10_CR33","doi-asserted-by":"crossref","unstructured":"N. Immerman, Descriptive and computational complexity, Computational Complexity Theory, J. Hartmanis (Ed.), Proc. Symp. Applied Math. 38, American Mathematical Society, pp. 75\u201391, 1989.","DOI":"10.1090\/psapm\/038\/1020810"},{"key":"10_CR34","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman, Nondeterministic space is closed under complementation, SIAM J. on Computing, 17, pp. 935\u2013938, 1988.","journal-title":"SIAM J. on Computing"},{"key":"10_CR35","doi-asserted-by":"crossref","unstructured":"R. Implagliazzo and D. Zuckerman, How to recycle random bits, Proc. of the 30th FOCS, pp. 248\u2013253, 1989.","DOI":"10.1109\/SFCS.1989.63486"},{"key":"10_CR36","doi-asserted-by":"crossref","unstructured":"D. Johnson, A catalog of complexity classes, Handbook of Theoretical Compluter Science, Vol. A, van Leeuwen (ed.), MIT Press\/ Elsvier, pp. 67\u2013162, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50007-2"},{"key":"10_CR37","unstructured":"P. Kanellakis, Private communication, 1986."},{"key":"10_CR38","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/BF02579140","volume":"4","author":"J. Kahn","year":"1984","unstructured":"J. Kahn, M. Saks, D. Sturtevant, A topological approach to evasiveness, Combinatorica 4, pp. 297\u2013306, 1984.","journal-title":"Combinatorica"},{"issue":"No2","key":"10_CR39","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/0403021","volume":"3","author":"M. Karchmer","year":"1990","unstructured":"M. Karchmer and A. Wigderson, Monotone circuits for connectivity require super-logarithmic depth, SIAM J. on Discrete Mathematics, Vol 3, No 2. pp. 255\u2013265, 1990.","journal-title":"SIAM J. on Discrete Mathematics"},{"key":"10_CR40","first-page":"130","volume":"25","author":"H. Lewis","year":"1982","unstructured":"H. Lewis and C. Papadimitriu, Symmetric space-bounded computation, Theoretical Computer Science 25, pp. 130\u2013143, 1982.","journal-title":"Theoretical Computer Science"},{"key":"10_CR41","doi-asserted-by":"crossref","unstructured":"N. Nisan, Pseudo-random generators for space-bounded computation, Proc. of the 22nd STOC, pp. 204\u2013212, 1990.","DOI":"10.1145\/100216.100242"},{"key":"10_CR42","doi-asserted-by":"crossref","unstructured":"N. Nisan, RL \u2208 SC, Proc. of the 24th STOC, pp. 619\u2013623, 1992.","DOI":"10.1145\/129712.129772"},{"key":"10_CR43","doi-asserted-by":"crossref","unstructured":"J. Naor and M. Naor, Small-bias probability spaces: efficient constuctions and applications, Proc. of the 22nd STOC, pp. 213\u2013223, 1990.","DOI":"10.1145\/100216.100244"},{"key":"10_CR44","unstructured":"N. Nisan, E. Szemeredi and A. Wigderson, Undirected connectivity in O(log1.5 n) space, submitted to FOCS '92."},{"key":"10_CR45","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Wigderson, Hardness vs. Randomness, Proc. of the 29th FOCS, pp. 2\u201312, 1988.","DOI":"10.1109\/SFCS.1988.21916"},{"key":"10_CR46","doi-asserted-by":"crossref","unstructured":"R. Raz and A. Wigderson, Probabilistic communication complexity of Boolean relations, Proc. of the 30th FOCS, pp. 562\u2013567, 1989.","DOI":"10.1109\/SFCS.1989.63535"},{"key":"10_CR47","doi-asserted-by":"crossref","unstructured":"R. Raz and A. Wigderson, Monotone circuits for matching require linear depth, Proc. of the 22nd STOC, pp. 287\u2013292, 1990.","DOI":"10.1145\/100216.100253"},{"key":"10_CR48","doi-asserted-by":"crossref","unstructured":"J. H. Reif, Symmetric complementation, Proc. of the 14th STOC, pp. 201\u2013214, 1982.","DOI":"10.1145\/800070.802193"},{"key":"10_CR49","first-page":"96","volume":"33","author":"R. Szelepcsenyi","year":"1987","unstructured":"R. Szelepcsenyi, The method of forcing for nondeterministic automata, Bull. of the European Ass. of Theoretical Computer Science, 33, pp. 96\u2013100, 1987.","journal-title":"Bull. of the European Ass. of Theoretical Computer Science"},{"key":"10_CR50","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. Savitch","year":"1970","unstructured":"W. Savitch, Relashionships between nondeterministic and deterministic tape complexities, Journal of Computer Systems and Sciences, 4, pp. 177\u2013192, 1970.","journal-title":"Journal of Computer Systems and Sciences"},{"key":"10_CR51","doi-asserted-by":"crossref","unstructured":"S. Skyum and L. Valiant, A complexity theory based on Boolean algebra, Proc. of the 22nd FOCS, pp. 244\u2013253, 1981.","DOI":"10.1109\/SFCS.1981.3"},{"issue":"1","key":"10_CR52","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1137\/0211010","volume":"11","author":"M. Tompa","year":"1982","unstructured":"M. Tompa, Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations, SIAM J. on Computing, 11, 1, pp. 130\u2013137, 1982.","journal-title":"SIAM J. on Computing"},{"key":"10_CR53","doi-asserted-by":"crossref","unstructured":"A. C. Yao, Some complexity questions related to distributive computing, Proc. of the 11th STOC, pp. 209\u2013213, 1979.","DOI":"10.1145\/800135.804414"},{"key":"10_CR54","unstructured":"A. C. Yao, Private communication."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1992"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55808-X_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:29:59Z","timestamp":1742592599000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55808-X_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540558088","9783540472919"],"references-count":54,"URL":"https:\/\/doi.org\/10.1007\/3-540-55808-x_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}