# Alternative proofs of Savitch's theorem?

Question: Are there any known proofs of Savitch's theorem that $$NL \subseteq L^2$$ besides the usual one?

By the usual one I mean the proof based on recursively querying whether there is a midpoint.

Whether a proof is different is subjective, but hopefully not too subjective for this forum.

What I Learned:

• A superficially different argument first shows graph reachability is in log-space uniform $$AC^1$$, by building a circuit calculating $$G^{|G|}$$ via repeating squaring, and then providing a depth first algorithm that shows that log-space uniform $$AC^1$$ is in $$L^2$$. (Reference: https://cs.stackexchange.com/a/90950/66344). I think the essential idea is the same.
• This paper offers a different formalization of Savitch's theorem as a game: https://link.springer.com/chapter/10.1007/978-3-642-11512-7_2 The intuition is nice, but the essential idea is the same.
• It seems that no improvements on Savitch's theorem are known ( https://rjlipton.wordpress.com/2009/04/05/savitchs-theorem/ ), but this is not the same question.
• This is a really neat question! I know that this isn't what you asked, but I thought it might be valuable to mention the following. It's my understanding that it's not known whether $NL \subseteq DTISP(2^{o(\log^2(n))}, \log^2(n))$. In other words, maybe a different approach could improve on Savitch's theorem by running in $2^{o(\log^2(n))}$ time. – Michael Wehar Feb 12 at 5:31