Omer Reingold
Skip Abstract Section
Abstract
We present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log4/3(⋅) 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 O(log n log log n)-space, deterministic algorithm for undirected st-connectivity.
Our algorithm also implies a way to construct in log-space a fixed 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.
- Ajtai, M., Komlós, J., and Szemerédi, E. 1987. Deterministic simulation in LOGSPACE. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC) (New York, NY). ACM, New York, 132--140. Google Scholar
Digital Library
- Aleliunas, R., Karp, R. M., Lipton, R. J., Lovász, L., and Rackoff, C. 1979. Random walks, universal traversal sequences, and the complexity of maze problems. In Proceedings of the 20th Annual Symposium on Foundations of Computer Science (FOCS) (San Juan, Puerto Rico). IEEE Computer Society Press, Los Alamitos, CA, 218--223. Google ScholarDigital Library
- Alon, N. 1986. Eigenvalues and expanders. Combinatorica 6, 2, 83--96. Google ScholarDigital Library
- Alon, N., Galil, Z., and Milman, V. D. 1987. Better expanders and superconcentrators. J. Algorithms 8, 3, 337--347. Google ScholarDigital Library
- Alon, N., and Milman, V. D. 1985. λ1, isoperimetric inequalities for graphs, and superconcentrators. J. Combinat. Theory Ser. B 38, 1, 73--88.Google ScholarCross Ref
- Alon, N., and Roichman, Y. 1994. Random Cayley graphs and expanders. Rand. Struct. Algorithms 5, 2, 271--284.Google ScholarDigital Library
- Alon, N., and Sudakov, B. 2000. Bipartite subgraphs and the smallest eigenvalue. Combinat. Probab. Comput. 9, 1. Google ScholarDigital Library
- Alvarez, C., and Greenlaw, R. 1996. A compendium of problems complete for symmetric logarithmic space. Electronic Colloquium on Computational Complexity (ECCC) 3, 039.Google Scholar
- Armoni, R., Ta-Shma, A., Wigderson, A., and Zhou, S. 2000. An o(log(n)4/3) space algorithm for (s,t) connectivity in undirected graphs. J. ACM 47, 2, 294--311. Google ScholarDigital Library
- Babai, L., Nisan, N., and Szegedy, M. 1989. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (Seattle, WA). ACM, New York, 204--232. Google ScholarDigital Library
- Ben-Asher, Y., Lange, K.-J., Peleg, D., and Schuster, A. 1995. The complexity of reconfiguring network model. Inf. Comput. 21, 1, 41--58. Google ScholarDigital Library
- Borodin, A., Cook, S. A., Dymond, P. W., Ruzzo, W. L., and Tompa, M. 1989. Two applications of inductive counting for complementation problems. SIAM J. Comput. (SICOMP) 18, 3, 559--578. Google ScholarDigital Library
- Broder, A., and Shamir, E. 1987. On the second eigenvalue of random regular graphs. In Poceedings of the 28th Annual Symposium on Foundations of Computer Science (FOCS) (Los Angeles, CA). IEEE Computer Society Press, Los Alamitos, CA, 286--294. Google ScholarDigital Library
- Chung, K.-M., Reingold, O., and Vadhan, S. 2007. S-T connectivity on digraphs with known stationary distribution. In Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC), In IEEE Computer Society Press, Los Alamitos, CA, 236--249. (Full version posted as ECCC TR07-030). Google ScholarDigital Library
- Dinur, I. 2007. The PCP Theorem by gap amplification. J. ACM 54, 3, 12. Google ScholarDigital Library
- Friedman, J. 1991. On the second eigenvalue and random walks in random d-regular graphs. Combinatorica 11, 4, 331--362.Google ScholarCross Ref
- Friedman, J., Kahn, J., and Szemerédi, E. 1989. On the second eigenvalue in random regular graphs. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing (Seattle, WA), ACM, New York, 587--598. Google ScholarDigital Library
- Gabber, O., and Galil, Z. 1981. Explicit constructions of linear-sized superconcentrators. J. Comput. Syst. Sci. 22, 3 (June), 407--420.Google ScholarCross Ref
- 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.)Google Scholar
- Goldreich, O. 2008. Computational Complexity: A Conceptual Perspective. Cambridge University Press. (Online drafts at http://www.wisdom.weizmann.ac.il/oded/cc-drafts.html.) Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Hoory, S., and Wigderson, A. 1993. Universal traversal sequences for expander graphs. Inf. Process. Lett. 46, 2, 67--69. Google ScholarDigital Library
- Impagliazzo, R., Nisan, N., and Wigderson, A. 1994. Pseudorandomness for network algorithms. In Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (STOC) (Montréal, Québec, Canada). ACM, New York, 356--364. Google ScholarDigital Library
- Jerrum, M., Sinclair, A., and Vigoda, E. 2004. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM 51, 4, 671--697. Google ScholarDigital Library
- Jimbo, S., and Maruoka, A. 1987. Expanders obtained from affine transformations. Combinatorica 7, 4, 343--355. Google ScholarDigital Library
- Karchmer, M., and Wigderson, A. 1993. On span programs. In Proceedings of the 8th Structures in Complexity conference. 102--111.Google Scholar
- Klivans, A., and van Melkebeek, D. 2002. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput. (SICOMP) 31, 5, 1501--1526. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Koucky, M. 2003. On traversal sequences, exploration sequences and completeness of kolmogorov random strings. Ph.D. dissertation, Rutgers University. Google ScholarDigital Library
- Lewis, H. R., and Papadimitriou, C. H. 1982. Symmetric space-bounded computation. Theoret. Comput. Sci. 19, 161--187.Google ScholarCross Ref
- Lubotzky, A., Phillips, R., and Sarnak, P. 1988. Ramanujan graphs. Combinatorica 8, 3, 261--277.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Margulis, G. A. 1973. Explicit constructions of expanders. Problemy Peredachi Informatsii 9, 4, 71--80.Google Scholar
- 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.Google Scholar
- Martin, R. A., and Randall, D. 2000. Sampling adsorbing staircase walks using a new markov chain decomposition method. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). (Redondo Beach, CA) IEEE Computer Society Press, Los Alamitos, CA, 492--502. Google ScholarDigital Library
- Morgenstern, M. 1994. Existence and explicit constructions of q + 1 regular Ramanujan graphs for every prime power q. J. Combinat. Theory Ser. B 62, 1, 44--62. Google ScholarDigital Library
- Nisan, N. 1992a. Pseudorandom generators for space-bounded computation. Combinatorica 12, 4, 449--461.Google ScholarCross Ref
- Nisan, N. 1992b. RL ⊆ SC. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, 619--623. Google ScholarDigital Library
- Nisan, N., Szemerédi, E., and Wigderson, A. 1989. Undirected connectivity in o(log1.5n) space. In Proceedings of the 30th Foundations of Computer Science (Research Triangle Park, NC), IEEE Computer Society Press, Los Alamitos, CA, 24--29. Google ScholarDigital Library
- Nisan, N., and Ta-Shma, A. 1995. Symmetric logspace is closed under complement. Chicago J. Theor. Comput. Sci.Google Scholar
- Nisan, N., and Zuckerman, D. 1996. Randomness is linear in space. J. Comput. Syst. Sci. 52, 1 (Feb.), 43--52. Google ScholarDigital Library
- Pinsker, M. S. 1973. On the complexity of a concentrator. In Proceedings of the 7th Annual Teletraffic Conference. Stockholm, 318/1--318/4.Google Scholar
- Raz, R., and Reingold, O. 1999. On recycling the randomness of the states in space bounded computation. In Proceedings of the 31st Annual ACM Symposium on the Theory of Computing (STOC) (Atlanta, GA). ACM, New York. Google ScholarDigital Library
- Reif, J. H. 1984. Symmetric complementation. J. ACM 31, 2, 401--421. Google ScholarDigital Library
- Reingold, O., Trevisan, L., and Vadhan, S. P. 2006. Pseudorandom walks on regular digraphs and the RL vs. L Problem. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, 457--466. Google ScholarDigital Library
- Reingold, O., Vadhan, S., and Wigderson, A. 2000. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS) (Redondo Beach, CA). IEEE Computer Society Press, Los Alamitos, CA, 3--13. Google ScholarDigital Library
- Reingold, O., Vadhan, S., and Wigderson, A. 2002. Entropy waves, the zig-zag graph product, and new constant-degree expanders. Ann. Math. 155, 1 (January). (Extended abstract in Proceedings of FOCS '00). Google ScholarDigital Library
- Rozenman, E., and Vadhan, S. 2005. Derandomized squaring of graphs. In Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM). Lecture Notes in Computer Science, vol. 3624. Springer-Verlag, New York, 436--447. Google ScholarDigital Library
- Saks, M. 1996. Randomization and derandomization in space-bounded computation. In Proceedings of the IEEE 11th Annual Conference on Structure in Complexity Theory. IEEE Computer Society Press, Los Alamitos, CA. Google ScholarDigital Library
- Saks, M., and Zhou, S. 1999. bphspace(S) ⊆ dspace(S3/2). J. Comput. Syst. Sci. 58, 2, 376--403. Google ScholarDigital Library
- Savitch, J. 1970. Relationship between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4, 2, 177--192.Google ScholarDigital Library
- Tanner, M. R. 1984. Explicit concentrators from generalized n-gons. SIAM J. Algeb. Disc. Meth. 5, 3, 287--293.Google ScholarCross Ref
- Trifonov, V. 2005. 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 (STOC). ACM, New York. Google ScholarDigital Library
- Wigderson, A. 1992. The complexity of graph connectivity. In Proceedings of the 17th Mathematical Foundations of Computer Science. 112--132. Google ScholarDigital Library
Index Terms
- Undirected connectivity in log-space
Recommendations
Undirected ST-connectivity in log-space
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computingWe present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log4/3 obtained by Armoni, Ta-Shma, Wigderson and Zhou [9]. As undirected st-...
Pseudorandomness when the odds are against you
CCC '16: Proceedings of the 31st Conference on Computational ComplexityImpagliazzo and Wigderson [25] showed that if E = DTIME(2O(n)) requires size 2Ω(n) circuits, then every time T constant-error randomized algorithm can be simulated deterministically in time poly(T). However, such polynomial slowdown is a deal breaker ...
Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates
We exhibit an explicitly computable pseudorandom generator stretching $l$ bits into $m(l) = l^{\Omega(\log l)}$ bits that look random to constant-depth circuits of size $m(l)$ with $\log m(l)$ arbitrary symmetric gates (e.g., PARITY, MAJORITY). This ...
Comments