What is the actual cost of derandomization? And can we get it for free? These questions were recently raised by Doron et. al (FOCS 2020) and have been attracting considerable interest. In this work we extend the study of these questions to the setting of *derandomizing interactive proofs systems*.
First, we show conditional derandomization of $\mathcal{MA}$ and of $\mathcal{AM}$ with *optimal runtime overhead*, where optimality is under the $\#\mathsf{NSETH}$ assumption. Specifically, denote by $\mathcal{AM}\mathcal{TIME}^{[\rightleftharpoons c]}[T]$ a protocol with $c$ turns of interaction in which the verifier runs in polynomial time $T$. We prove that for every $\epsilon>0$ there exists $\delta>0$ such that:
1. $\mathcal{MATIME}[T]\subseteq \mathcal{NTIME}[T^{2+\epsilon}]$,
2. $\mathcal{AM}\mathcal{TIME}^{[\rightleftharpoons c]}[T] \subseteq \mathcal{NTIME}[n\cdot T^{\ceil{c/2}+\epsilon}]$,
assuming the existence of properties of Boolean functions that can be recognized quickly from the function's truth-table such that functions with the property are hard for proof systems that receive near-maximal amount of non-uniform advice.
To obtain faster derandomization, we introduce the notion of a *deterministic doubly efficient argument system*. This is a doubly efficient proof system in which the verifier is *deterministic*, and the soundness is relaxed to be computational, as follows: For every probabilistic polynomial-time adversary $\tilde{P}$, the probability that $\tilde{P}$ finds an input $x\notin L$ and misleading proof $\pi$ such that $V(x,\pi)=1$ is negligible.
Under strong hardness assumptions, we prove that *any constant-round doubly efficient proof system can be compiled into a deterministic doubly efficient argument system, with essentially no time overhead*. As one corollary, under strong hardness assumptions, for every $\epsilon>0$ there is a deterministic verifier $V$ that gets an $n$-bit formula $\Phi$ of size $2^{o(n)}$, runs in time $2^{\epsilon \cdot n}$, and satisfies the following: An honest prover running in time $2^{O(n)}$ can print, for every $\Phi$, a proof $\pi$ such that $V(\Phi,\pi)$ outputs the number of satisfying assignments for $\Phi$; and for every adversary $\tilde{P}$ running in time $2^{O(n)}$, the probability that $\tilde{P}$ finds $\Phi$ and $\pi$ such that $V(\Phi,\pi)$ outputs an incorrect count is $2^{-\omega(n)}$.
We modified the definition of our deterministic argument systems to restrict the honest prover's running time, and adapted the result statements accordingly. In addition we relaxed a main condition in the hypothesis of the argument system for #SAT. Lastly, we improved the exposition a bit, and fixed minor local issues in the technical sections.
What is the actual cost of derandomization? And can we get it for free? These questions were recently raised by Doron et. al (FOCS 2020) and have been attracting considerable interest. In this work we extend the study of these questions to the setting of *derandomizing interactive proofs systems*.
First, we show conditional derandomization of $\mathcal{MA}$ and of $\mathcal{AM}$ with *optimal runtime overhead*, where optimality is under the $\#NSETH$ assumption. Specifically, denote by $\mathcal{AM}\mathcal{TIME}^{[\rightleftharpoons c]}[T]$ a protocol with $c$ turns of interaction in which the verifier runs in polynomial time $T$. We prove that for every $\epsilon>0$ there exists $\delta>0$ such that:
1. $\mathcal{MATIME}[T]\subseteq \mathcal{NTIME}[T^{2+\epsilon}]$, and
2. $\mathcal{AM}\mathcal{TIME}^{[\rightleftharpoons c]}[T] \subseteq \mathcal{NTIME}[n\cdot T^{\lceil c/2 \rceil+\epsilon}]$,
where $(1)$ follows if there is a property $\Pi$ of Boolean functions that can be recognized from a $2^n$-length truth-table in $\mathcal{NTIME}[2^{(2+\epsilon/3)\cdot n}]$ such that functions with $\Pi$ are hard for $(\mathcal{N}\cap co\mathcal{N})\mathcal{TIME}[2^{(2-\delta)\cdot n}]/2^{(1-\delta)\cdot n}$; and $(2)$ follows if for every $k\ge1$ there is a $\Pi$ that can be recognized from a $2^n$-length truth-table in $\mathcal{NTIME}[2^{(k+\epsilon/3)\cdot n}]$ such that functions with $\Pi$ are hard for $\mathcal{MAMTIME}[2^{(1-\delta)\cdot k n}]/2^{(1-\delta)\cdot n}$.
To obtain faster derandomization, we introduce the notion of a *deterministic effective argument system*: This is a deterministic verifier $V$ such that correct claims $x\in L$ can be proved to $V$ (i.e., there is a proof $\pi$ such that $V(x,\pi)=1$), and for every probabilistic polynomial-time adversary $\tilde{P}$, the probability that $\tilde{P}$ finds an incorrect claim $x\notin L$ and a misleading proof $\pi$ such that $V(x,\pi)=1$ is negligible.
Under strong hardness assumptions, we prove that *any constant-round proof system can be compiled into a deterministic effective argument system, with essentially no time overhead*. As one corollary, under the foregoing hardness assumptions, for every $\epsilon>0$ there is a deterministic verifier $V$ that gets as input an $n$-bit formula of size $2^{o(n)}$, runs in time $2^{\epsilon \cdot n}$, and satisfies the following: For every formula $\Phi$ there is a proof $\pi$ such that $V(\Phi,\pi)$ prints the number of satisfying assignments for $\Phi$; and for every adversary $\tilde{P}$ running in time $2^{O(n)}$, the probability that $\tilde{P}$ finds $\Phi$ and $\pi$ such that $V(\Phi,\pi)$ prints an incorrect count is $2^{-\omega(n)}$.
