Pseudorandom walks on regular digraphs and the RL vs. L problem

ABSTRACT

We revisit the general RL vs. L question, obtaining the following results.

• Generalizing Reingold's techniques to directed graphs, we present a deterministic, log-space algorithm that given a regular directed graph G (or, more generally, a digraph with Eulerian connected components) and two vertices s and t, finds a path between s and t if one exists.
• If we restrict ourselves to directed graphs that are regular and consistently labelled, then we are able to produce pseudorandom walks for such graphs in logarithmic space (this result already found an independent application).
• We prove that if (2) could be generalized to all regular directed graphs (including ones that are not consistently labelled) then L=RL. We do so by exhibiting a new complete promise problem for RL, and showing that such a problem can be solved in deterministic logarithmic space given a log-space pseudorandom walk generator for regular directed graphs.

REFERENCES

• 1: M. Ajtai , J. Komlos , E. Szemeredi, Deterministic simulation in LOGSPACE, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.132-140, January 1987, New York, New York, United States [doi>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 Proc. 20th FOCS, pp. 218--223, 1979.
• 3: Roy Armoni , Amnon Ta-Shma , Avi Widgerson , Shiyu Zhou, An O(log(n)4/3) space algorithm for (s, t) connectivity in undirected graphs, Journal of the ACM (JACM), v.47 n.2, p.294-311, March 2000 [doi>10.1145/333979.333984]
• 4: László Babai , Noam Nisan , Márió Szegedy, Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs, Journal of Computer and System Sciences, v.45 n.2, p.204-232, Oct. 1992 [doi>10.1016/0022-0000(92)90047-M]
• 5: S. Caracciolo, A. Pelissetto, and A. Sokal. Two remarks on simulated tempering. Unpublished manuscript (see {13}), 1992.
• 6: J. A. Fill. Eigenvalue bounds on convergence to stationarity for nonreversible markov chains with an application to the exclusion process. Ann. Applied Probability, 1:62--87, 1991.
• 7: I. Haitner, D. Harnik, and O. Reingold. On the power of the randomized iterate. ECCC TR05-135, 2005.
• 8: Alexander Healy , Salil Vadhan , Emanuele Viola, Using nondeterminism to amplify hardness, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007389]
• 9: P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.189, November 12-14, 2000
• 10: E. Kaplan, M. Naor, and O. Reingold. Derandomized constructions of k-wise (almost) independent permutations. In Proc. 8th RANDOM, Springer LNCS 3624, pp. 354 -- 365, 2005.
• 11: H. R. Lewis and C. H. Papadimitriou. Symmetric space-bounded computation. Theor. Comput. Sci., 19:161--187, 1982.
• 12: L. Lovász. Combinatorial problems and exercises. North-Holland, Amsterdam, 2nd ed., 1993.
• 13: N. Madras and D. Randall. Markov chain decomposition for convergence rate analysis. Ann. of Applied Probability, 12:581--606, 2002.
• 14: R. A. Martin , D. Randall, Sampling adsorbing staircase walks using a new Markov chain decomposition method, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.492, November 12-14, 2000
• 15: M. Mihail. Conductance and convergence of markov chains: a combinatorial treatment of expanders. In Proc. 37th FOCS, pp. 526--531, 1989.
• 16: Noam Nisan, RL⊆SC, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.619-623, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129772]
• 17: N. Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449--461, 1992.
• 18: N. Nisan, E. Szemeredi, and A. Wigderson. Undirected connectivity in o(log1.5n) space. In Proc. 30th FOCS, pp. 24--29, 1989.
• 19: Noam Nisan , David Zuckerman, Randomness is linear in space, Journal of Computer and System Sciences, v.52 n.1, p.43-52, Feb. 1996 [doi>10.1006/jcss.1996.0004]
• 20: Omer Reingold, Undirected ST-connectivity in log-space, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060647]
• 21: O. Reingold, L. Trevisan, and S. Vadhan. Pseudorandom walks in biregular graphs and the RL vs. L problem. ECCC TR05-022, 2005.
• 22: O. Reingold, S. Vadhan, and A. Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders. Ann. Mathematics, 155(1), 2001.
• 23: E. Rozenman and S. Vadhan. Derandomized squaring of graphs. In Proc. 8th RANDOM, Springer LNCS 3624, pp. 436--447, 2005. See also full version, ECCC TR05-92.
• 24: Michael Saks, Randomization and Derandomization in Space-Bounded Computation, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, p.128, May 24-27, 1996
• 25: Michael Saks , Shiyu Zhou, BPH SPACE(S) ⊆ DSPACE(S3/2), Journal of Computer and System Sciences, v.58 n.2, p.376-403, April 1999 [doi>10.1006/jcss.1998.1616]
• 26: J. Savitch. Relationship between nondeterministic and deterministic tape complexities. J. Computer and System Sci., 4(2):177--192, 1970.
• 27: Alistair Sinclair , Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, v.82 n.1, p.93-133, July 1989 [doi>10.1016/0890-5401(89)90067-9]
• 28: D. Sivakumar, Algorithmic derandomization via complexity theory, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509996]
• 29: Avi Wigderson, The Complexity of Graph Connectivity, Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science, p.112-132, August 24-28, 1992

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

General Terms:
Algorithms, Theory

Keywords:
derandomization, expander graphs, mixing time, space-bounded computation, universal traversal sequence, zig-zag product