Undirected ST-connectivity in log-space

By Omer Reingold. Symposium on the Theory of Computing, 2005

309 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/babf2d64bd4ffc44657adcaa23c3dc9781e9b5cb

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Scott Aaronson
2. Anton Bovier
3. Irina A. Kurkova

In Computer Networks and Communications

1. Scott Aaronson
2. Anton Bovier
3. Irina A. Kurkova

Citations in the corpus

• Poisson convergence in the restricted k-partitioning problem (2007, background): “It is possible to recognize connectivity in undirected graphs with a randomized log-space algorithm using random walks [1] (also, a deterministic log-space algorithm was recently discovered [25]).”
• Quantum computing, postselection, and probabilistic polynomial-time (2004, background): “[10] succeeded with a quite (2)A few examples are primality testing in deterministic polynomial time [7], undirected graph connectivity in log-space [30], and inapproximability of the 3-SAT problem unless P = NP [32].”