Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #4 to TR22-093 | 8th January 2023 03:30

More Verifier Efficient Interactive Protocols For Bounded Space

RSS-Feed




Revision #4
Authors: Joshua Cook
Accepted on: 8th January 2023 03:30
Downloads: 236
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, 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.



Changes to previous version:

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.


Revision #3 to TR22-093 | 26th October 2022 00:36

More Verifier Efficient Interactive Protocols For Bounded Space





Revision #3
Authors: Joshua Cook
Accepted on: 26th October 2022 00:36
Downloads: 203
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, 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.



Changes to previous version:

Added abstract back to ECCC, fixed some typos.


Revision #2 to TR22-093 | 26th October 2022 00:15

More Verifier Efficient Interactive Protocols For Bounded Space





Revision #2
Authors: Joshua Cook
Accepted on: 26th October 2022 00:15
Downloads: 213
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)].$$



Changes to previous version:

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.


Revision #1 to TR22-093 | 4th October 2022 22:22

More Verifier Efficient Interactive Protocols For Bounded Space





Revision #1
Authors: Joshua Cook
Accepted on: 4th October 2022 22:22
Downloads: 254
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, 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.



Changes to previous version:

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.


Paper:

TR22-093 | 28th June 2022 03:50

More Verifier Efficient Interactive Protocols For Bounded Space


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