More Verifier Efficient Interactive Protocols for Bounded Space
| Autor: | Cook, Joshua |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: | |
| DOI: | 10.4230/lipics.fsttcs.2022.14 |
| Popis: | 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 co-nondeterministic 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. LIPIcs, Vol. 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022), pages 14:1-14:18 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|