Kai-Min Chung
Abstract
We present a deterministic logspace algorithm for solving S-T Connectivity on directed graphs if: (i) we are given a stationary distribution of the random walk on the graph in which both of the input vertices s and t have nonnegligible probability mass and (ii) the random walk which starts at the source vertex s has polynomial mixing time. This result generalizes the recent deterministic logspace algorithm for S-T Connectivity on undirected graphs [Reingold, 2008]. It identifies knowledge of the stationary distribution as the gap between the S-T Connectivity problems we know how to solve in logspace (L) and those that capture all of randomized logspace (RL).
- Aldous, D. and Fill, J. A. 2001. Reversible markov chains and random walks on graphs. Monograph in preparation, http://www.stat.berkeley.edu/~aldous/RWG/book.html.Google Scholar
- 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. IEEE, 218--223. Google ScholarDigital Library
- Amit, A., Linial, N., Matousek, J., and Rozenman, E. 2001. Random lifts of graphs. In Proceedings of the Annual ACM/SIAM Symposium on Discrete Algorithms (SODA). 883--894. Google ScholarDigital Library
- Blum, M. and Micali, S. 1984. How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput. 13, 4, 850--864. Google ScholarDigital Library
- Chung, K.-M., Reingold, O., and Vadhan, S. 2007. S-t connectivity on digraphs with a known stationary distribution. In Proceedings of the IEEE Conference on Computational Complexity. Google ScholarDigital Library
- Fill, J. A. 1991. Eigenvalue bounds on convergence to stationarity for nonreversible markov chains with an application to the exclusion process. Ann. Appl. Probab. 1, 62--87.Google ScholarCross Ref
- Haitner, I., Harnik, D., and Reingold, O. 2006. On the power of the randomized iterate. In Proceedings of the Annual International Cryptology Conference (CRYPTO). 22--40. Google ScholarDigital Library
- Impagliazzo, R., Kabanets, V., and Wigderson, A. 2002. In search of an easy witness: exponential time vs. probabilistic polynomial time. J. Comput. Syst. Sci. 65, 4, 672--694. Google ScholarDigital Library
- Indyk, P. 2000. Stable distributions, pseudorandom generators, embeddings and data stream computation. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science. IEEE, 189--197. Google ScholarDigital Library
- Kabanets, V. and Impagliazzo, R. 2004. Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex. 13, 1-2, 1--46. Google ScholarDigital Library
- Kaplan, E., Naor, M., and Reingold, O. 2005. Derandomized constructions of k-wise (almost) independent permutations. In Proceedings of the International Workshop on Approximation Algorithms for Combinational Optimization (APPROX-RANDOM). 354--365. Google ScholarDigital Library
- Lawler, G. F. and Sokal, A. D. 1988. Bounds on the l2 spectrum for markov chains and markov processes: A generalization of cheeger's inequality. Trans. Amer. Math. Soc. 309, 2, 557--580.Google Scholar
- Mihail, M. 1989. Conductance and convergence of markov chains: A combinatorial treatment of expanders. In Proceedings of the 37th Conference on Foundations of Computer Science. 526--531. Google ScholarDigital Library
- Nisan, N. 1992. Pseudorandom generators for space-bounded computation. Combinatorica 12, 4, 449--461.Google ScholarCross Ref
- Nisan, N. and Wigderson, A. 1994. Hardness vs randomness. J. Comput. Syst. Sci. 49, 2, 149--167. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Reingold, O. 2008. Undirected connectivity in log-space. J. ACM 55, 4. Google ScholarDigital Library
- Reingold, O., Trevisan, L., and Vadhan, S. 2006. Pseudorandom walks in regular digraphs and the RL vs. L problem. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC‘06). 457--466. Google ScholarDigital Library
- Reingold, O., Vadhan, S., and Wigderson, A. 2001. Entropy waves, the zig-zag graph product, and new constant-degree expanders. Ann. Math. 155, 1.Google Scholar
- Saks, M. and Zhou, S. 1999. BPhSPACE(S) ⊆ SPACE(S). J. Comput. Syst. Sci. 58, 2, 376--403. Google ScholarDigital Library
- Sinclair, A. and Jerrum, M. 1989. Approximate counting, uniform generation and rapidly mixing Markov chains. Inf. Comput. 82, 1, 93--133. Google ScholarDigital Library
- Sivakumar, D. 2002. Algorithmic derandomization via complexity theory. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing. ACM, New York, 619--626. Google ScholarDigital Library
- Tanner, M. R. 1984. Explicit concentrators from generalized n-gons. SIAM J. Algebr. Discr. Methods 5, 3, 287--293.Google ScholarCross Ref
- Trifonov, V. 2005. An O(log n log log n) space algorithm for undirected st-connectivity. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC). 626--633. Google ScholarDigital Library
- Yao, A. C. 1982. Theory and applications of trapdoor functions (extended abstract). In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. IEEE, 80--91. Google ScholarCross Ref
Index Terms
- S-T connectivity on digraphs with a known stationary distribution
Recommendations
S-T Connectivity on Digraphs with a Known Stationary Distribution
CCC '07: Proceedings of the Twenty-Second Annual IEEE Conference on Computational ComplexityWe present a deterministic logspace algorithm for solving S-T CONNECTIVITY on directed graphs if (i) we are given a stationary distribution for random walk on the graph and (ii) the random walk which starts at the source vertex s has polynomial mixing ...
Restricted arc-connectivity of digraphs
Since interconnection networks are often modeled by graphs or digraphs, the edge-connectivity of a graph or arc-connectivity of a digraph are important measurements for fault tolerance of networks. The restricted edge-connectivity @l^'(G) of a graph G ...
Derandomizing isolation in space-bounded settings
CCC '17: Proceedings of the 32nd Computational Complexity ConferenceWe study the possibility of deterministic and randomness-efficient isolation in space-bounded models of computation: Can one efficiently reduce instances of computational problems to equivalent instances that have at most one solution? We present ...
Comments