USTCONN is the problem that requires deciding whether there is a path from the source vertex $s$ to the target vertex $t$ in a graph $G$, where these are all given as part of the input.
Omer Reingold showed that USTCONN is in L (doi:10.1145/1391289.1391291). The proof constructs a constant-degree expander by means of the zig-zag product. A constant-degree expander has logarithmic diameter and one can then check all the possible paths using a constant number of logarithmic-size markers.
Reingold's result gives a logarithmic upper bound on the space complexity of USTCONN, resolving its space complexity "up to a constant factor" according to the paper. I am curious about the corresponding lower bound, which is not mentioned anywhere else in the paper.
How does one prove that logarithmic space is required to decide USTCONN in the worst case?
Edit: Fix the input representation to be the $N \times N$ adjacency matrix of the underlying $N$-vertex symmetric simple directed graph, with the rows listed consecutively to form an $N^2$-bit string.
Lewis and Papadimitriou showed (doi:10.1016/0304-3975(82)90058-5) that USTCONN is SL-complete, which with Reingold's result implies that SL=L. Savitch showed (doi:10.1016/S0022-0000(70)80006-X) that $\text{NSPACE}(n) \subseteq \text{DSPACE}(n^2)$. Further $\text{DSPACE}(f(n)) = \text{DSPACE}(1)$ for any computable function $f(n) = o(\log\log n)$ by Stearns, Hartmanis and Lewis (doi:10.1109/FOCS.1965.11), so at least $\Omega(\log\log n)$ space is needed for USTCONN. Finally, the usual classes known to be below L (such as $\text{NC}^1$) are defined in terms of circuits and are not obviously comparable to any class defined in terms of a space bound.
As far as I can see, this leaves open the (admittedly unlikely) possibility that there is an even better deterministic algorithm that only uses $O((\log n)^\delta)$ but $\Omega(\log \log n)$ space, for some $\delta < 1$, or even a nondeterministic algorithm for USTCONN that uses $o((\log n)^{1/2})$ space.
By the space hierarchy theorem, $\text{DSPACE}(o(f(n)) \subsetneq \text{DSPACE}(f(n))$ as long as $f(n)$ is space-constructible. This might seem to suggest that USTCONN cannot be in $\text{DSPACE}(o(\log n))$. However, USTCONN being complete for L under logspace reductions does not seem to imply this. It seems still possible that USTCONN has enough structure to encode any problem in L by means of a logspace reduction, yet USTCONN itself only requires sublogarithmic space.
As long as there is some language in L that does require logarithmic space, then showing that USTCONN is complete for L under a strictly "weaker" than logspace reduction would yield the desired lower bound.
Is USTCONN complete for L under a reduction that requires $o(\log n)$ space?
Immerman showed (doi:10.1137/0216051) that a version of directed reachability in which the desired path (but not the graph itself) is deterministic, is complete for L under first-order reductions, which are computable by AC$^0$ circuits. This might then perhaps be adapted to show that USTCONN is complete for L under FO-reductions. However, although AC$^0$ is strictly contained in L, AC$^0$ is again a circuit class and I am not aware of any way to perform FO-reductions in sublogarithmic space.
Edit 2015-07-14: It is an interesting philosophical issue whether the space usage of a TM should include the size of an index into the input (thus allowing random access into the input, but needing an extra bit if the input doubles in size), or whether the space used by a TM is the number of worktape squares visited during a computation (which assumes that the input tape head is fixed and does not change when the input tape doubles in size). The former RAM-style definition immediately gives a logspace lower bound for any computation, and models current computers that keep track of the current position in a file as an offset from the start of the file. The latter classical definition assumes a paper-like tape with a fixed read head that doesn't know anything about the tape other than the current input symbol, which possibly is what Turing intended in his 1937 paper.
Heuristic arguments like the comment by Thomas, that it is not even possible to index the input with $o(\log n)$ bits of space, appear to assume a modern RAM-style definition. Stearns/Hartmanis/Lewis use the TM-style definition, as does most classical work in space-bounded computation.
One can prove a logspace lower bound for USTCONN represented as an adjacency matrix by noting that the unary language of perfect squares requires logspace to recognise (see Rūsiņš Freivalds, Models of Computation, Riemann Hypothesis, and Classical Mathematics, SOFSEM 1998, LNCS 1521, 89–106. doi:10.1007/3-540-49477-4_6 (preprint)). Then the same lower bound applies to USTCONN with the adjacency matrix representation. This is perhaps too much of a cheat: usually enforcing the promise in a promise problem is meant to be easy compared to the actual problem, but here enforcing the promise that the input is a graph already gives the lower bound. So it would be nice to see an argument for a logspace lower bound for the promise problem where the input is guaranteed to be from the language $\{\{0,1\}^{N \times N} \mid N=1,2,\dots\}$.
