Tight Lower bounds on Savitch's theorem First of all, I apologize in advance for any stupidity. I am by no means an expert on complexity theory (far from it! I am an undergraduate taking my first class in complexity theory) Here's my question. Now Savitch's Theorem states that 
$$\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^2\right)$$
Now I'm curious if if this lower bound was tight, i.e that is something along the lines of 
$\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^{1.9}\right)$ is not achievable. 

It seems like something there should be a straightforward combinatorial argument to be made here - each node in the configuration graph for a Deterministic Turing machine has only one outgoing edge, while each node in the configuration graph of a Non-Deterministic Turing machine can have more than one outgoing edge. What Savitch's algorithm is doing is converting configuration graphs with any number outgoing edge to configuration graphs with $&lt;2$ outgoing edges.

Since the configuration graph defines a unique TM (not sure about this), the combinatorial size of the latter is almost certainly larger than the former. This "difference" is perhaps a factor of $n^2$, perhaps less - I don't know. Of course, there are lots of little technical issues to be worked out, like how you need to make sure there are no loops and so forth, but my question is if this is a reasonable way to begun proving a thing like this.&nbsp;
This is a well known open question. You will see in complexity theory many open questions for which you'd wonder how come no one managed to solve them. Part of the reason is that we need new people like you to help us solve them :)

For the latest result in this area, showing that Savitch's algorithm is optimal in some restricted model, see Aaron Potechin's FOCS paper.

Specifically, he starts from the nice observation that because the configuration graph of a deterministic TM has only one outgoing edge (after fixing the input), one can think of it as an undirected graph, and so the question becomes something like the following: given a directed graph $G$ of $n$ vertices with two special vertices $s,t$, if we map it to an $N$ vertex undirected graph $G'$ (also with special vertices $s',t'$) such that the existence of each edge in $G'$ depends on one edge in $G$ and there is a path from $s$ to $t$ in $G$ iff there's a path between $s'$ and $t'$ in $G'$, how much bigger $N$ has to be from $n$.

To show that Savitch's algorithm is optimal, one needs to show that $N$ has to be at least $2^{\Omega(\log^2 n)}  = n^{\Omega(\log n)}$. To show $L\neq NL$, it suffices to show the weaker bound that $N > n^c$ for every constant $c$.  I'm pretty sure that even $N > n^{10}$ is not known, though perhaps something like $N \geq n^2$ is known for some not so interesting reasons.