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.APPROX/RANDOM.2023.47
URN: urn:nbn:de:0030-drops-188727
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18872/
Go to the corresponding LIPIcs Volume Portal

Cook, Joshua ; Rothblum, Ron D.

Efficient Interactive Proofs for Non-Deterministic Bounded Space

pdf-format:
LIPIcs-APPROX47.pdf (0.9 MB)

Abstract

The celebrated IP = PSPACE Theorem gives an efficient interactive proof for any bounded-space algorithm. In this work we study interactive proofs for non-deterministic bounded space computations. While Savitch’s Theorem shows that nondeterministic bounded-space algorithms can be simulated by deterministic bounded-space algorithms, this simulation has a quadratic overhead. We give interactive protocols for nondeterministic algorithms directly to get faster verifiers.
More specifically, for any non-deterministic space S algorithm, we construct an interactive proof in which the verifier runs in time Õ(n+S²). This improves on the best previous bound of Õ(n+S³) and matches the result for deterministic space bounded algorithms, up to polylog(S) factors.
We further generalize to alternating bounded space algorithms. For any language L decided by a time T, space S algorithm that uses d alternations, we construct an interactive proof in which the verifier runs in time Õ(n + S log(T) + S d) and the prover runs in time 2^O(S). For d = O(log(T)), this matches the best known interactive proofs for deterministic algorithms, up to polylog(S) factors, and improves on the previous best verifier time for nondeterministic algorithms by a factor of log(T). We also improve the best prior verifier time for unbounded alternations by a factor of S.
Using known connections of bounded alternation algorithms to bounded depth circuits, we also obtain faster verifiers for bounded depth circuits with unbounded fan-in.

BibTeX - Entry

@InProceedings{cook_et_al:LIPIcs.APPROX/RANDOM.2023.47,
  author =	{Cook, Joshua and Rothblum, Ron D.},
  title =	{{Efficient Interactive Proofs for Non-Deterministic Bounded Space}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{47:1--47:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18872},
  URN =		{urn:nbn:de:0030-drops-188727},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.47},
  annote =	{Keywords: Interactive Proofs, Alternating Algorithms, AC0\lbrack2\rbrack, Doubly Efficient Proofs}
}

Keywords: Interactive Proofs, Alternating Algorithms, AC0[2], Doubly Efficient Proofs
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Issue Date: 2023
Date of publication: 04.09.2023

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