Let $\mathbf{TISP}[T, S]$, $\mathbf{BPTISP}[T, S]$, $\mathbf{NTISP}[T, S]$ and $\mathbf{coNTISP}[T, S]$ be the set of languages recognized by deterministic, randomized, nondeterministic, and co-nondeterministic algorithms, respectively, running in time $T$ and space $S$. Let $\mathbf{ITIME}[T_V, T_P]$ be the set of languages recognized by an interactive protocol where the verifier runs in time $T_V$ and the prover runs in time $T_P$.

For $S = \Omega(\log(n))$ and $T$ constructible in time $\log(T) S + n$, we prove:
$$\mathbf{TISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T) S + n), 2^{O(S)}]$$
$$\mathbf{BPTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T) S + n), 2^{O(S)}]$$
$$\mathbf{NTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T)^2 S + n), 2^{O(S)}]$$
$$\mathbf{coNTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T)^2 S + n), 2^{O(S)}] .$$

The best prior verifier time is from Shamir:
$$\mathbf{TISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T)(S + n)), 2^{O(\log(T)(S + n))}]. $$
Our prover is faster, and our verifier is faster when $S = o(n)$.

The best prior prover time uses ideas from Goldwasser, Kalai, and Rothblum:
$$\mathbf{NTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T) S^2 + n), 2^{O(S)}].$$
Our verifier is faster when $\log(T) = o(S)$, and for deterministic algorithms.

To our knowledge, no previous interactive protocol for $\mathbf{TISP}$ simultaneously has the same verifier time and prover time as ours. In our opinion, our protocol is also simpler than previous protocols.

Fixed a slight bug in the claimed performance of the nondeterministic protocol case. We claimed the verifier ran in time
log(T)^2 S + n
but only showed a verifier which ran in time
log(T)^2 S + log(T) n.
This can be a large difference for NSPACE[n^{1/3}]. I have now updated the paper to prove the stronger claim. This required updating the arithemtization to include a more space efficient, but less time efficient variation, and requires using a second interactive protocol for nondeterministic algorithms to avoid calculating M^ directly with a large field.

I also added an efficient arithmetization of multitape Turing Machines to the appendix. This is (by constant factors) less efficient than arithmetizing the RAM algorithm directly, but the simpler instruction set allows a more complete proof than provided for RAM algorithms. This is probably what I should have used in the main paper, if I would have proved it earlier.

Let $\mathbf{TISP}[T, S]$, $\mathbf{BPTISP}[T, S]$, $\mathbf{NTISP}[T, S]$ and $\mathbf{coNTISP}[T, S]$ be the set of languages recognized by deterministic, randomized, nondeterministic, and co-nondeterministic algorithms, respectively, running in time $T$ and space $S$. Let $\mathbf{ITIME}[T_V, T_P]$ be the set of languages recognized by an interactive protocol where the verifier runs in time $T_V$ and the prover runs in time $T_P$.

For $S = \Omega(\log(n))$ and $T$ constructible in time $\log(T) S + n$, we prove:
$$\mathbf{TISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T) S + n), 2^{O(S)}]$$
$$\mathbf{BPTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T) S + n), 2^{O(S)}]$$
$$\mathbf{NTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T)^2 S + n), 2^{O(S)}]$$
$$\mathbf{coNTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T)^2 S + n), 2^{O(S)}] .$$

The best prior verifier time is from Shamir:
$$\mathbf{TISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T)(S + n)), 2^{O(\log(T)(S + n))}]. $$
Our prover is faster, and our verifier is faster when $S = o(n)$.

The best prior prover time uses ideas from Goldwasser, Kalai, and Rothblum:
$$\mathbf{NTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T) S^2 + n), 2^{O(S)}].$$
Our verifier is faster when $\log(T) = o(S)$, and for deterministic algorithms.

To our knowledge, no previous interactive protocol for $\mathbf{TISP}$ simultaneously has the same verifier time and prover time as ours. In our opinion, our protocol is also simpler than previous protocols.

Added abstract back to ECCC, fixed some typos.

Let $\mathbf{TISP}[T, S]$, $\mathbf{BPTISP}[T, S]$, $\mathbf{NTISP}[T, S]$, and $\mathbf{CoNTISP}[T, S]$ be the set of languages recognized by deterministic, randomized, nondeterminsitic, and co-nondeterministic algorithms, respectively, running in time $T$ and space $S$. Let $\mathbf{ITIME}[T_V]$ be the set of languages recognized by an interactive protocol where the verifier runs in time $T_V$. We prove:
$$\mathbf{TISP}[T, S] \cup \mathbf{BPTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T) S + n)]$$
$$\mathbf{NTISP}[T, S] \cup \mathbf{CoNTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T)^2 S + n)]$$
The prior most verifier time efficient interactive protocol for $\mathbf{TISP}$ uses ideas from Goldwasser, Kalai and Rothblum, which gives
$$\mathbf{NTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T) S^2 + n)].$$

Added a reference to Thaler's work: "Time-Optimal Interactive Proofs for Circuit Evaluation", which includes the same protocol for repeated matrix squaring. That work however did not apply it to bounded space computation, so our work still seems novel.

Let $\mathbf{TISP}[T, S]$, $\mathbf{BPTISP}[T, S]$, $\mathbf{NTISP}[T, S]$ and $\mathbf{coNTISP}[T, S]$ be the set of languages recognized by deterministic, randomized, nondeterministic, and co-non\-det\-er\-min\-is\-tic algorithms, respectively, running in time $T$ and space $S$. Let $\mathbf{ITIME}[T_V, T_P]$ be the set of languages recognized by an interactive protocol where the verifier runs in time $T_V$ and the prover runs in time $T_P$.

For $S = \Omega(\log(n))$ and $T$ constructible in time $\log(T) S + n$, we prove:
$$\mathbf{TISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T) S + n), 2^{O(S)}]$$
$$\mathbf{BPTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T) S + n), 2^{O(S)}]$$
$$\mathbf{NTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T)^2 S + n), 2^{O(S)}]$$
$$\mathbf{coNTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T)^2 S + n), 2^{O(S)}] .$$

The best prior verifier time is from Shamir:
$$\mathbf{TISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T)(S + n)), 2^{O(\log(T)(S + n))}]. $$
Our prover is faster, and our verifier is faster when $S = o(n)$.

The best prior prover time uses ideas from Goldwasser, Kalai, and Rothblum:
$$\mathbf{NTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T) S^2 + n), 2^{O(S)}].$$
Our verifier is faster when $\log(T) = o(S)$, and for deterministic algorithms.

To our knowledge, no previous interactive protocol for $\mathbf{TISP}$ simultaneously has the same verifier time and prover time as ours. In our opinion, our protocol is also simpler than previous protocols.

Near total rewrite of the paper to improve presentation and strengthen the prior results. The results and protocol are unchanged, only the presentation and comparisons with other work. A few notable changes.

1. Updated Shamir's previous protocol to be based on the bounded space variation, and not Shen's modification as it was previously.
2. Added a more detailed explanation for arithmetization and moved it out of preliminaries.
3. Paper no longer assumes reader knows sum check and includes a proof of sum check.
4. Greatly expanded proof idea to give more details.
5. More modular proof, proving the protocol in smaller lemmas instead of all at once.
6. Added a table of different interactive protocols for easy comparison.
7. Added more emphasis to the low space setting, where my protocol has a more clear advantage over Shamir's.
8. Updated preliminaries to include a more formal definition of computation path.
9. Many other spelling and grammatical fixes, and much, much more.

Let $\mathbf{TISP}[T, S]$, $\mathbf{BPTISP}[T, S]$, $\mathbf{NTISP}[T, S]$, and $\mathbf{CoNTISP}[T, S]$ be the set of languages recognized by deterministic, randomized, nondeterminsitic, and co-nondeterministic algorithms, respectively, running in time $T$ and space $S$. Let $\mathbf{ITIME}[T_V]$ be the set of languages recognized by an interactive protocol where the verifier runs in time $T_V$. We prove:
$$\mathbf{TISP}[T, S] \cup \mathbf{BPTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T) S + n)]$$
$$\mathbf{NTISP}[T, S] \cup \mathbf{CoNTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T)^2 S + n)]$$
The prior most verifier time efficient interactive protocol for $\mathbf{TISP}$ uses ideas from Goldwasser, Kalai and Rothblum, which gives
$$\mathbf{NTISP}[T, S] \subseteq \mathbf{ITIME}[\tilde{O}(\log(T) S^2 + n)].$$