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.

asked Feb 12, 2020 at 1:24

Elle Najt

1,4398 silver badges19 bronze badges

1

$\begingroup$ 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. $\endgroup$
– Michael Wehar
Feb 12, 2020 at 5:31

Add a comment |

0 Your Answer

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.