Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR22-093 | 28th June 2022 03:50

#### More Verifier Efficient Interactive Protocols For Bounded Space

TR22-093
Authors: Joshua Cook
Publication: 3rd July 2022 10:09
Keywords:

Abstract:

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)].$$

ISSN 1433-8092 | Imprint