ECCC-Report TR22-057https://eccc.weizmann.ac.il/report/2022/057Comments and Revisions published for TR22-057en-usMon, 25 Apr 2022 10:50:36 +0300
Paper TR22-057
| When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems |
Lijie Chen,
Roei Tell
https://eccc.weizmann.ac.il/report/2022/057What 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)}$.Mon, 25 Apr 2022 10:50:36 +0300https://eccc.weizmann.ac.il/report/2022/057