Efficient logspace algorithms It is easy to see that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). Many known logspace algorithms (For example : undirected st-connectivity, planar graph isomorphism) run in $O(n^k)$ where $k$ is insanely large.


I am looking for examples of natural problems that are known to be solvable simultaneously in deterministic logspace and $O(n^k)$ time where $k \leq 10$. There is nothing special about 10. Looking at the currently known logspace algorithms, I think $k \leq 10$ is interesting enough.
Aleliunas et al. showed that undirected st-connectivity is in $RL$ (randomized logspace). The running time of their algorithm is $O(n^3)$. Are there natural problems that can be solved simultaneously in $RL$ and linear time (or) near linear time i. e., $O(n{\log}^i{n})$ time ?


Edit : To make things more interesting let's look at problems that are at least $NC^1$-hard.
I guess Single-source Single-sink Planar DAG (SSPD) reachability has logspace algorithm with a modest running time ($O(n^2)$?). I am not so sure about
Single-source Multiple-sink Planar DAG Reachability (SMPD) algorithm.

Ref: Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Planar and Grid Graph Reachability Problems. Theory Comput. Syst. 45(4): 675-723 (2009)

Also, a new logspace algorithm for planarity testing and embedding runs in modestly polynomial time (modulo undirected reachability, of course)

Ref: Samir Datta, Gautam Prakriya: Planarity Testing Revisited CoRR abs/1101.2637: (2011)

Finally, here is a simple toy problem which has a logspace algo with a modest
running time (modulo undirected reachability) viz. Outerplanar Isomorphism.