%ACook, Joshua%ARothblum, Ron%AMegow, Nicole Ed.%ASmith, Adam Ed.%D2023%ISchloss Dagstuhl – Leibniz-Zentrum für Informatik
%KInteractive Proofs; Alternating Algorithms; AC0[2]; Doubly Efficient Proofs; Theory of computation → Interactive proof systems
%MOSTI ID: 10499097
%PMedium: X
%TEfficient Interactive Proofs for Non-Deterministic Bounded Space
%XThe 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.
Country unknown/Code not availablehttps://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.47OSTI-MSA