Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-057 | 25th April 2022 04:33

When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems


Authors: Lijie Chen, Roei Tell
Publication: 25th April 2022 10:50
Downloads: 191


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)}$.

ISSN 1433-8092 | Imprint