License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2022.14
URN: urn:nbn:de:0030-drops-174067
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17406/
Go to the corresponding LIPIcs Volume Portal

Cook, Joshua

More Verifier Efficient Interactive Protocols for Bounded Space

pdf-format:
LIPIcs-FSTTCS-2022-14.pdf (0.8 MB)

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 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.

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:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17406},
  URN =		{urn:nbn:de:0030-drops-174067},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI