Undirected connectivity in log-space
By Omer Reingold. JACM, 2008
600 citations recorded by the source corpus.
Subfields: Computational Theory and Mathematics, Computer Networks and Communications
View Paper: https://www.semanticscholar.org/paper/6b4d585a7920cc1324842c5f1ac9d0b123261525
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
- Diego Calvanese
- Gregory Valiant
- Andrei A. Bulatov
- Stefan Wager
- Jacob Steinhardt
- Larry A. Wasserman
- Sivaraman Balakrishnan
- Jayadev Acharya
In Computer Networks and Communications
- Diego Calvanese
- Roman Kontchakov
- Michael Zakharyaschev
- Alessandro Artale
- Gregory Valiant
- Andrei A. Bulatov
- Stefan Wager
- Jacob Steinhardt
Citations in the corpus
- Memory, Communication, and Statistical Queries (2016, background): “Finally, there is a large body of work on memory bounded computation from the theory community (e.g., Reingold, 2008), and work on the applied side on reducing the memory needs (e.g., Langford et al., 2009; Xiao, 2010; Agarwal et al., 2012; Mitliagkas et al., 2013; Arora et al., 2013; Steinhardt et…”
- The DL-Lite Family and Relations (2009, background): “On the other hand, the undirected graph reachability problem is known to be in LogSpace (Reingold, 2008) but not in AC.”
- A Dichotomy Theorem for Nonuniform CSPs (2017, methodology): “1Using the s − t-Connectivity algorithm by Reingold [53] this reduction can be improved to a log-space one.”