Abstract
In this paper we survey the major developments in understanding the complexity of the graph connectivity problem in several computational models, and highlight some challenging open problems.
Preview
Unable to display preview. Download preview PDF.
References
M. Ajtai, On the complexity of the pigeonhole principle, Proc. of the 29th FOCS, pp. 346–355, 1988.
M. Ajtai, First-order definability on finite structures, Annals of Pure and Applied Logic, 45, pp. 211–225, 1989.
M. Ajtai and M. Ben-Or, A theorem on probabilistic constant-depth computation, Proc. of the 16th STOC, pp. 471–474, 1984.
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–150, 1990.
M. Ajtai, J. Komlos, E. Szemeredi, Deterministic simulation in logspace, Proc. of the 19th STOC, pp. 132–140, 1987.
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–223, 1979.
P. Berman and J. Simon, Lower bounds for graph threading by probabilistic machines, Proc. of the 24th FOCS, pp. 304–311, 1983.
B. Bollobas, Extremal Graph Theory, Academic Press, 1978.
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.
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–578, 1989.
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–220.
M. Blum and S. Micali, How to generate cryptographically strong sequences of pseudo-random bits, SIAM J. on Computing, 13, 4, pp. 850–864, 1984.
L. Babai, N. Nisan and M. Szegedy, Multi-party protocols and logspacehard pseudo-random sequences, Proc. of the 21st STOC, pp.1–11, 1989.
G. Barnes and W. L. Ruzzo, Deterministic algorithms for undirected st-connectivity using polynomial time and sublinear space, Proc. 23rd STOC, pp. 43–53, 1991.
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–804, 1990.
L. Carter and M. Wegman, Universal hash functions, J. of Computer Systems and Sciences, 18, 2, pp. 143–154, 1979.
S. A. Cook, A taxonomy of problems with fast parallel algorithms, Information and Computation, 64, pp. 2–22, 1985.
A. Cohen and A. Wigderson, Dispersers, deterministic amplification and weak random sources, Proc. of the 30th FOCS, pp. 14–19, 1989.
D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, Proc. of the 19th STOC, pp. 1–6, 1987.
A. Chandra, M. Furst and R. J. Lipton, Multi-party protocols, Proc. of the 15th STOC, pp. 94–99, 1983.
M. Chrobak, H. Karloff, T. Radzik, Connectivity vs. reachability, Information and Computation, Vol 91, No 2, pp. 177–188, 1991.
S. Cook and P. McKenzie, manuscript, 1986.
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–652, 1980.
H. B. Enderton, A Mathematical Introduction to Logic, Academic Press, 1972.
A. Ehrenfeucht, An application of games to the completeness problem for formalized theories, Fund. Math., 49, pp. 129–141, 1961.
R. Fagin, Monadic generalized spectra, Seitschrift fur Mathematische Logik und Grundlagen der Mathematik, Vol 21, pp. 89–96, 1975.
R. Fraisse, Sur les classifications des systems de relations, Publications Scientifiques de l'Université d'Alger, Vol 1. pp. 35–182, 1954.
M. Furst, J. Saxe and M. Sipser, Parity, circuits and the polynomial-time hierarchy, Math System Theory 17, pp. 13–27, 1984.
M. Grigni and M. Sipser, Monotone complexity, Proceedings of LMS workshop on Boolean function complexity, Durham, M. Paterson (Ed.), Cambridge University Press, 1990.
M. Grigni and M. Sipser, Monotone separation of Logspace from NC 1, Proc. of the 6th Structures in Complexity Theory conference, pp. 294–298, 1991.
J. Hastad, Computational limitations of small-depth circuits, The MIT Press, 1987.
S. Istrail, Polynomial traversing sequences for cycles are constructible, Proc. of the 20th STOC, pp. 491–503, 1988.
N. Immerman, Descriptive and computational complexity, Computational Complexity Theory, J. Hartmanis (Ed.), Proc. Symp. Applied Math. 38, American Mathematical Society, pp. 75–91, 1989.
N. Immerman, Nondeterministic space is closed under complementation, SIAM J. on Computing, 17, pp. 935–938, 1988.
R. Implagliazzo and D. Zuckerman, How to recycle random bits, Proc. of the 30th FOCS, pp. 248–253, 1989.
D. Johnson, A catalog of complexity classes, Handbook of Theoretical Compluter Science, Vol. A, van Leeuwen (ed.), MIT Press/ Elsvier, pp. 67–162, 1990.
P. Kanellakis, Private communication, 1986.
J. Kahn, M. Saks, D. Sturtevant, A topological approach to evasiveness, Combinatorica 4, pp. 297–306, 1984.
M. Karchmer and A. Wigderson, Monotone circuits for connectivity require super-logarithmic depth, SIAM J. on Discrete Mathematics, Vol 3, No 2. pp. 255–265, 1990.
H. Lewis and C. Papadimitriu, Symmetric space-bounded computation, Theoretical Computer Science 25, pp. 130–143, 1982.
N. Nisan, Pseudo-random generators for space-bounded computation, Proc. of the 22nd STOC, pp. 204–212, 1990.
N. Nisan, RL ∈ SC, Proc. of the 24th STOC, pp. 619–623, 1992.
J. Naor and M. Naor, Small-bias probability spaces: efficient constuctions and applications, Proc. of the 22nd STOC, pp. 213–223, 1990.
N. Nisan, E. Szemeredi and A. Wigderson, Undirected connectivity in O(log1.5 n) space, submitted to FOCS '92.
N. Nisan and A. Wigderson, Hardness vs. Randomness, Proc. of the 29th FOCS, pp. 2–12, 1988.
R. Raz and A. Wigderson, Probabilistic communication complexity of Boolean relations, Proc. of the 30th FOCS, pp. 562–567, 1989.
R. Raz and A. Wigderson, Monotone circuits for matching require linear depth, Proc. of the 22nd STOC, pp. 287–292, 1990.
J. H. Reif, Symmetric complementation, Proc. of the 14th STOC, pp. 201–214, 1982.
R. Szelepcsenyi, The method of forcing for nondeterministic automata, Bull. of the European Ass. of Theoretical Computer Science, 33, pp. 96–100, 1987.
W. Savitch, Relashionships between nondeterministic and deterministic tape complexities, Journal of Computer Systems and Sciences, 4, pp. 177–192, 1970.
S. Skyum and L. Valiant, A complexity theory based on Boolean algebra, Proc. of the 22nd FOCS, pp. 244–253, 1981.
M. Tompa, Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations, SIAM J. on Computing, 11, 1, pp. 130–137, 1982.
A. C. Yao, Some complexity questions related to distributive computing, Proc. of the 11th STOC, pp. 209–213, 1979.
A. C. Yao, Private communication.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wigderson, A. (1992). The complexity of graph connectivity. In: Havel, I.M., Koubek, V. (eds) Mathematical Foundations of Computer Science 1992. MFCS 1992. Lecture Notes in Computer Science, vol 629. Springer, Berlin, Heidelberg . https://doi.org/10.1007/3-540-55808-X_10
Download citation
DOI: https://doi.org/10.1007/3-540-55808-X_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55808-8
Online ISBN: 978-3-540-47291-9
eBook Packages: Springer Book Archive