Before going to prove this result, we look at something simpler first, which also introduces the easy witness method:

Theorem 1: At least one of the following holds:

- For every $\varepsilon>0$, any language in $\mathrm{RP}$ can be simulated in $\mathrm{DTIME}(2^{n^\varepsilon})$ such that no language in $\mathrm{ZPP}$ can refute the simulation io.
- $\mathrm{BPP}=\mathrm{ZPP}$.

More formally, for given randomized algorithm $A(x,r)$ on input $x,|x|=n$ and random bits $r,|r|=m=n^a$ for some constant $a$, let $S^{\delta}_m$ be the set of truth tables of all $\lceil \log m\rceil$-variable Boolean functions with low circuit complexity (at most $m^\delta$). Hence $S^{\delta}_m$ contains strings of length $m$, and it can be enumerated in $\mathrm{DTIME}(2^{n^{2\delta}})$. Therefore checking for all $\alpha \in {S^{\delta}_m}$ if $R(x,\alpha)$ accepts takes time at most $(2^{n^\varepsilon})$ for $\delta = \varepsilon/(2a)$. Let this algorithm be $B^{\varepsilon}_{A}(x)$.

If this algorithm $B^{\varepsilon}_{A}$ works for every $A \in \mathrm{RP}$ and $\varepsilon>0$, then (1) holds and we are done. Otherwise, there exists $A$,$\varepsilon>0$ and an expected polynomial time refuter $R(1^n)\in\{0,1\}^n$ such that, for almost all $n$, $B^{\varepsilon}_{A}(R(1^{n}))$ does not accept whereas $A(R(1^{n}),r)$ accepts for some $r$. Therefore $A(R(1^{n}),r)$ can be viewed as a Boolean circuit $C^{\mathrm{hard}}(r)$ which accepts almost all $m$-bit strings and all accepted strings are truth tables of a $\log m$-variable Boolean function with the smallest circuit size at least $m^{\varepsilon/(2a)}$. Since $R(1^{n})$ halts in polynomial time with high probability, we have an algorithm in $\mathrm{ZPP}$ which can construct such circuits $C^{\mathrm{hard}}$.

Given such a circuit $C^{\mathrm{hard}}$, we can guess a string uniformly at random $\beta\in\{0,1\}^m$ which $C^{\mathrm{hard}}$ accepts. Reminding ourselves of IW result:

Impagliazzo-Wigderson Generator: Given $r\in\{0,1\}^{n^c}$, truth table of a circuit on $c \log n$-Boolean variables with circuit complexity at least $n^{\varepsilon c}$, there exists $c,d\in\mathbb{N}$ and a polynomial time computable generator $G_r(s):\{0,1\}^{d \log n} \rightarrow \{0,1\}^n$ with hardness $H(G_r)> n$.

If we use this $\beta$ to construct the generator $G_{\beta}$ of IW mapping $\{0,1\}^{d \log k}$ to $\{0,1\}^k$, we get a generator $G_{\beta}$ with hardness greater than $k$ for sufficiently large $k$. Constructing these takes expected polynomial time, and last step takes deterministic polynomial time, therefore for every $L \in \mathrm{BPP}$, we have $L \in \mathrm{ZPP}$. QED

Instead of IW generator, we can use Babai-Fortnow-Nisan-Wigderson generator, to arrive at the following result.

Theorem 2: At least one of the following holds:

- Any language in $\mathrm{RP}$ can be simulated in $\mathrm{DTIME}(2^{(\log n)^{\log\log n}})$ such that no language in $\mathrm{ZPP}$ can refute the simulation io.
- $\mathrm{BPP}\subseteq \mathrm{ZPSUBEXP}$ where $\mathrm{ZPSUBEXP}$ denotes the class of languages with an expected sub exponential time algorithm.

Instead of fiddling with the generator, we can increase the power of refuter. In Theorem 1, when first condition fails, we can allow the refuter to take expected sub exponential time. After changing the circuit size and parameters appropriately, we have the following result:

Theorem 3: At least one of the following holds:

- For every $\varepsilon>0$, any language in $\mathrm{RP}$ can be simulated in $\mathrm{DTIME}(2^{n^{\varepsilon}})$ such that no language in $\mathrm{ZPSUBEXP}$ can refute the simulation io.
- $\mathrm{BPP}\subseteq \mathrm{ZPSUBEXP}$.

Corollary 1: For every $\varepsilon>0$, any language in $\mathrm{RP}$ can be simulated in $\mathrm{ZPTIME}(2^{n^{\varepsilon}})$ such that no language in $\mathrm{ZPSUBEXP}$ can refute the simulation io.

Notice that above results imply that we can get analogous results to the ones obtained in IW paper:

In IW, assuming $\mathrm{BPP}\neq \mathrm{EXP}$, deterministic subexponential time bound was shown for $\mathrm{BPP}$. Using the machinery developed above, we can answer a weaker question: What happens when $\mathrm{ZPP}\neq \mathrm{EXP}$?

Theorem 4: If $\mathrm{ZPP}\neq \mathrm{EXP}$, then any language in $\mathrm{RP}$ can be simulated in $\mathrm{DTIME}(2^{n^{\varepsilon}})$ for all $\varepsilon>0$ such that no language in $\mathrm{ZPP}$ can refute the simulation io.

Proof: Assume otherwise. Then by Theorem 1, $\mathrm{BPP}=\mathrm{ZPP}$. But for some $\varepsilon>0$, $\mathrm{BPP}$ is a proper subset of $\mathrm{DTIME}(2^{n^\varepsilon})$ for $\mathrm{BPP}$ refuters (by Time Hierarchy Theorem). Using IW theorem, this implies

$\mathrm{BPP} = \mathrm{EXP} = \mathrm{ZPP}$. QED

The gap theorem of IW (either no derandomization of BPP is possible, or BPP can be simulated in deterministic $2^{n^\varepsilon}$ time for every $\varepsilon>0$) can be shown for ZPP as follows:

Theorem 5: Either $\mathrm{ZPP}=\mathrm{EXP}$ or for every $\varepsilon>0$, any language in $\mathrm{RP}$ can be simulated in $\mathrm{DTIME}(2^{n^{\varepsilon}})$ for all $\varepsilon>0$ such that no language in $\mathrm{ZPP}$ can refute the simulation io.

Proof: Assume $\mathrm{ZPP}=\mathrm{EXP} = \mathrm{RP}$. By Time Hierarchy Theorem, for every $\varepsilon>0$, $\mathrm{EXP}$ is not in $\mathrm{DTIME}(2^{n^\varepsilon})$ with $\mathrm{ZPP}$ refuters. Thus at most one of the conditions holds. By Theorem 4, at least one of the conditions holds. The result follows. QED

Notice that "easy witness'' method applies even when the refuters are allowed to be non-deterministic Turing machines, and by essentially using the same proof structure, we can obtain the following result:

Theorem 6: At least one of the following holds:

- For every $\varepsilon>0$, any language in $\mathrm{NP}$ can be simulated in $\mathrm{DTIME}(2^{n^\varepsilon})$ such that no language in $\mathrm{NP}$ can refute the simulation io.
- $\mathrm{BPP}\subseteq \mathrm{NP}$.

## No comments:

## Post a Comment

Note: Only a member of this blog may post a comment.