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 constant $\epsilon>0$,
\begin{align*}
\mathcal{MATIME}[T]&\subseteq \mathcal{NTIME}[T^{2+\epsilon}] \;, \\
\mathcal{AM}\mathcal{TIME}^{[\rightleftharpoons c]}[T] &\subseteq \mathcal{NTIME}[n\cdot T^{\lceil{c/2\rceil}+\epsilon}] \;,
\end{align*}
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 effective argument system. This is an $\mathcal{NP}$-type 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 effective 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)}$.
Reorganized and revised the introduction; streamlined and simplified the high-level technical section; added more explanations about the hypothesis used when derandomizing deIP into deARG; added an explanation about the connection to the Fiat-Shamir heuristic; added an explicit statement about deARG systems for DTISP[poly(n),n^{eps}], using [RRR16]; added explicit statements about worst-case derandomization of AM with imperfect completeness; relaxed the hypothesis used for the deARG system for #SAT; various low-level corrections.
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)}$.
