Abstract
Let TISP[T, S], BPTISP[T, S], NTISP[T, S] and CoNTISP[T, S] be the set of languages recognized by deterministic, randomized, nondeterministic, and conondeterministic algorithms, respectively, running in time T and space S. Let 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 = Ω(log(n)) and T constructible in time log(T) S + n, we prove:
TISP[T, S] ⊆ ITIME[Õ(log(T) S + n), 2^O(S)]
BPTISP[T, S] ⊆ ITIME[Õ(log(T) S + n), 2^O(S)]
NTISP[T, S] ⊆ ITIME[Õ(log(T)^2 S + n), 2^O(S)]
CoNTISP[T, S] ⊆ ITIME[Õ(log(T)^2 S + n), 2^O(S)] .
The best prior verifier time is from Shamir [Shamir, 1992; Lund et al., 1990]: TISP[T, S] ⊆ ITIME[Õ(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 [Goldwasser et al., 2015]:
NTISP[T, S] ⊆ ITIME[Õ(log(T) S² + 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 TISP simultaneously has the same verifier time and prover time as ours. In our opinion, our protocol is also simpler than previous protocols.
BibTeX  Entry
@InProceedings{cook:LIPIcs.FSTTCS.2022.14,
author = {Cook, Joshua},
title = {{More Verifier Efficient Interactive Protocols for Bounded Space}},
booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
pages = {14:114:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772617},
ISSN = {18688969},
year = {2022},
volume = {250},
editor = {Dawar, Anuj and Guruswami, Venkatesan},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17406},
URN = {urn:nbn:de:0030drops174067},
doi = {10.4230/LIPIcs.FSTTCS.2022.14},
annote = {Keywords: Interactive Proofs, Verifier Time, Randomized Space, Nondeterministic Space, Fine Grain Complexity}
}
Keywords: 

Interactive Proofs, Verifier Time, Randomized Space, Nondeterministic Space, Fine Grain Complexity 
Collection: 

42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) 
Issue Date: 

2022 
Date of publication: 

14.12.2022 