2026-07-22T14:08:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17406 2024-03-06T10:59:40Z ddc:004 open_access

More Verifier Efficient Interactive Protocols for Bounded Space Cook, Joshua Interactive Proofs Verifier Time Randomized Space Nondeterministic Space Fine Grain Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joshua Cook 2022 Is Part Of LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2022.14 urn:nbn:de:0030-drops-174067 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.14 eng https://creativecommons.org/licenses/by/4.0/legalcode