Undirected \(st\)-connectivity in log-space. (English) Zbl 1192.68374
STOC’05: Proceedings of the 37th annual ACM symposium on theory of computing, Baltimore, MD, USA, May 22–24, 2005. New York, NY: Association for Computing Machinery (ACM) (ISBN 1-58113-960-8). 376-385 (2005).
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C40 | Connectivity |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | M. Ajtai, J. Komlós, and E. Szemerédi. Deterministic simulation in LOGSPACE. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 132-140, 1987. 10.1145/28395.28410 |
| [2] | R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász, and C. Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In 20th Annual Symposium on Foundations of Computer Science, pages 218-223. IEEE, 1979. |
| [3] | N. Alon. Eigenvalues and expanders. Combinatorica, 6(2):83-96, 1986. 10.1007/BF02579166 · Zbl 0661.05053 |
| [4] | N. Alon, Z. Galil, and V. D. Milman. Better expanders and superconcentrators. Journal of Algorithms, 8(3):337-347, 1987. 10.1016/0196-6774(87)90014-9 · Zbl 0641.68102 |
| [5] | N. Alon and V. D. Milman. λsb 1, isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory. Series B, 38(1):73-88, 1985. · Zbl 0549.05051 |
| [6] | N. Alon and Y. Roichman. Random Cayley graphs and expanders. Random Structures & Algorithms, 5(2):271-284, 1994. · Zbl 0798.05048 |
| [7] | N. Alon and B. Sudakov. Bipartite subgraphs and the smallest eigenvalue. Combinatorics, Probability & Computing, 9(1), 2000. 10.1017/S0963548399004071 · Zbl 0945.05041 |
| [8] | C. Alvarez and R. Greenlaw. A compendium of problems complete for symmetric logarithmic space. Electronic Colloquium on Computational Complexity (ECCC), 3(039), 1996. |
| [9] | R. Armoni, A. Ta-Shma, A. Wigderson, and S. Zhou. An o(log(n)4/3) space algorithm for (s,t) connectivity in undirected graphs. Journal of the ACM, 47(2):294-311, 2000. 10.1145/333979.333984 · Zbl 1133.68341 |
| [10] | L. Babai, N. Nisan, and M. Szegedy. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. Journal of Computer and System Sciences, pages 204-232. 10.1016/0022-0000(92)90047-M · Zbl 0769.68040 |
| [11] | A. Borodin, S. A. Cook, P. W. Dymond, W. L. Ruzzo, and M. Tompa. Two applications of inductive counting for complementation problems. SIAM J. Comput., 18(3):559-578, 1989. 10.1137/0218038 · Zbl 0678.68031 |
| [12] | A. Broder and E. Shamir. On the second eigenvalue of random regular graphs. In 28th FOCS, pages 286-294, 1987. |
| [13] | J. Friedman. On the second eigenvalue and random walks in random d-regular graphs. Combinatorica, 11(4):331-362, 1991. · Zbl 0760.05078 |
| [14] | J. Friedman, J. Kahn, and E. Szemerédi. On the second eigenvalue in random regular graphs. In 21st STOC, pages 587-598, 1989. 10.1145/73007.73063 |
| [15] | O. Gabber and Z. Galil. Explicit constructions of linear-sized superconcentrators. J. Comput. Syst. Sci., 22(3):407-420, June 1981. · Zbl 0487.05045 |
| [16] | O. Goldreich and A. Wigderson. Derandomization that is rarely wrong from short advice that is typically good. In RANDOM, pages 209-223, 2002. · Zbl 1028.68225 |
| [17] | S. Hoory and A. Wigderson. Universal traversal sequences for expander graphs. Inf. Process. Lett., 46(2):67-69, 1993. 10.1016/0020-0190(93)90199-J · Zbl 0770.68069 |
| [18] | R. Impagliazzo, N. Nisan, and A. Wigderson. Pseudorandomness for network algorithms. In 26th STOC, pages 356-364, 1994. 10.1145/195058.195190 · Zbl 1345.68269 |
| [19] | S. Jimbo and A. Maruoka. Expanders obtained from affine transformations. Combinatorica, 7(4):343-355, 1987. 10.1007/BF02579322 · Zbl 0637.05017 |
| [20] | M. Karchmer and A. Wigderson. On span programs. In Proc. of the 8th Structures in Complexity conference, pages 102-111, 1993. |
| [21] | A. Klivans and D. van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput., 31(5):1501-1526, 2002. 10.1137/S0097539700389652 · Zbl 1016.68060 |
| [22] | M. Koucky. Universal traversal sequences with backtracking. In IEEE Conference on Computational Complexity, pages 21-27, 2001. |
| [23] | M. Koucky. On traversal sequences, exploration sequences and completeness of Kolmogorov random strings. PhD thesis, Rutgers University, 2003. |
| [24] | H. R. Lewis and C. H. Papadimitriou. Symmetric space-bounded computation. Theor. Comput. Sci., 19:161-187, 1982. · Zbl 0491.68045 |
| [25] | A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261-277, 1988. · Zbl 0661.05035 |
| [26] | N. Madras and D. Randall. Factoring markov chains to bound mixing rates. In 37th FOCS, pages 194-203, 1996. |
| [27] | G. A. Margulis. Explicit constructions of expanders. Problemy Peredaci Informacii, 9(4):71-80, 1973. · Zbl 0312.22011 |
| [28] | G. A. Margulis. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24(1):51-60, 1988. · Zbl 0708.05030 |
| [29] | R. A. Martin and D. Randall. Sampling adsorbing staircase walks using a new markov chain decomposition method. In 41st FOCS, pages 492-502, 2000. |
| [30] | M. Morgenstern. Existence and explicit constructions of q+1 regular Ramanujan graphs for every prime power q. Journal of Combinatorial Theory. Series B, 62(1):44-62, 1994. 10.1006/jctb.1994.1054 · Zbl 0814.68098 |
| [31] | Nisan. RL ⊆ SC. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 619-623, 1992. 10.1145/129712.129772 |
| [32] | N. Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449-461, 1992. · Zbl 0759.68024 |
| [33] | N. Nisan, E. Szemeredi, and A. Wigderson. Undirected connectivity in o(log1.5n) space. In Proceedings of the 30th FOCS, pages 24-29. IEEE, 1989. · Zbl 0915.05081 |
| [34] | N. Nisan and A. Ta-Shma. Symmetric logspace is closed under complement. Chicago J. Theor. Comput. Sci., 1995. · Zbl 0924.68039 |
| [35] | N. Nisan and D. Zuckerman. Randomness is linear in space. J. Comput. Syst. Sci., 52(1):43-52, Feb. 1996. 10.1006/jcss.1996.0004 · Zbl 0846.68041 |
| [36] | M. S. Pinsker. On the complexity of a concentrator. In 7th Annual Teletraffic Conference, pages 318/1-318/4, 1973. |
| [37] | R. Raz and O. Reingold. On recycling the randomness of the states in space bounded computation. In 31st STOC, 1999. 10.1145/301250.301294 · Zbl 1345.68135 |
| [38] | J. H. Reif. Symmetric complementation. J. ACM, 31(2):401-421, 1984. 10.1145/62.322436 · Zbl 0632.68062 |
| [39] | O. Reingold, L. Trevisan, and S. Vadhan. Pseudorandom walks in biregular graphs and the RL vs. L problem. ECCC Technical Report TR05-022, 2005. |
| [40] | O. Reingold, S. Vadhan, and A. Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders. Annals of Mathematics, 155(1), 2001. Extended abstract in Proc. of FOCS ‘00. |
| [41] | M. Saks. Randomization and derandomization in space-bounded computation. In IEEE 11th Annual Conference on Structure in Complexity Theory, 1996. |
| [42] | M. Saks and S. Zhou. rm bp sb rm h rm space(S) ⊆ rm dspace(S sp 3/2). Journal of Computer and System Sciences, 58(2):376-403, 1999. 36th IEEE Symposium on the Foundations of Computer Science. 10.1006/jcss.1998.1616 · Zbl 0922.68083 |
| [43] | J. Savitch. Relationship between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177-192, 1970. · Zbl 0188.33502 |
| [44] | M. R. Tanner. Explicit concentrators from generalized n-gons. SIAM Journal on Algebraic Discrete Methods, 5(3):287-293, 1984. · Zbl 0554.05045 |
| [45] | V. Trifonov. An o(log n log log n) space algorithm for undirected s,t-connectivity. In Proceedings of the 37th ACM Symposium on Theory of Computing, 2005. 10.1145/1060590.1060684 |
| [46] | A. Wigderson. The complexity of graph connectivity. In Proceedings of the 17th Mathematical Foundations of Computer Science, pages 112-132, 1992. · Zbl 1493.68163 |
| [47] | D. P. Y. Ben-Asher, K. Lange and A. Schuster. The complexity of reconfiguring network model. Information and Computation, 21(1):41-58, 1995. 10.1006/inco.1995.1122 · Zbl 0832.68045 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
