Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?

Question

There are assumptions that are known to imply that $P = BPP$. For example, if there exists a function in $E = DTIME(2^{O(n)})$ that has circuit complexity $2^{\Omega(n)}$, then $P = BPP$ [1]. Clearly, such a result would also imply that $P = ZPP$.

Is there an assumption that is known to imply $P = ZPP$ but is not known to imply that $P = BPP$? Alternatively, is there a reason to believe that such a result is unlikely to exist?

[1] Impagliazzo, Russell, and Avi Wigderson. "P= BPP if E requires exponential circuits: Derandomizing the XOR lemma." Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. 1997.

Answer 1

I think it is "easy" to come up with an assumption that implies one but not necessarily the other... (just write down a condition that is equivalent to P=ZPP)... however, a "natural" and non-uniform assumption (e.g. some weak form of PRG) seems harder, since (for example) hitting set generators (the non-uniform thing you need for P=RP) imply pseudorandom generators (what you need for P=BPP).

---

Just to give an idea of how annoying the problem is, here is a "natural" non-uniform condition that implies P=ZPP but (oops) also implies hitting sets, so it also implies P=BPP.

Say a circuit pair $(C,C')$ is good for length $n$ if $C$ and $C'$ have the same number of inputs, and for every input $x$ of length $n$,

$(Pr_y[C(x,y)=1]>2/3 \wedge Pr_y[C'(x,y)=0]=1)$ XOR $(Pr_y[C'(x,y)=1]>2/3 \wedge Pr_y[C(x,y)=0]=1)$.

Intuitively, these pairs can model any $RP \cap coRP = ZPP$ function.

To prove $P=ZPP$, it would suffice to have for all $\epsilon > 0$, a polynomial time function which given $1^n$, prints a set $S$ of $poly(n)$ strings of length up to $n$ such that for all circuit pairs $(C,C')$ with size $n$ that are good for length $m=n^{\epsilon}$, and all $x$ of length $m$, $(\exists y \in S)[C(x,y)=1 \vee C'(x,y)=1]$. (This should suffice, since by definition of "good", for all $x$, it cannot be that both $C$ and $C'$ have some input $y$ making them accept. I set $m=n^{\epsilon}$ to keep the condition from being too strong for other reasons.)

The main point is that the hitting set $S$ above "only" has to work for good circuit pairs. Nevertheless, this constraint isn't enough to keep from getting a full hitting set. Consider any circuit $C$ with $\Pr_x[C(x)=1]>2/3$. Write the inputs of $C$ over "$y$-variables" instead of $x$-variables. Look at the circuit pair $(0,C)$, where $0$ is the circuit which outputs zero on all inputs $(x,y)$. This pair trivially satisfies the goodness condition ($C$ and $0$ have the same behavior on all inputs $x$, because they do not depend on $x$ at all). And if there is always an $a \in S$ such that $[C(x,a)=1 \vee 0(x,a) = 1]$ is true, then $S$ is just a hitting set.

You could try to require some "non-trivialness" condition on top of that (say that each circuit in the pair can't be trivial), but the patches I can think of could also be circumvented.

It would be interesting if there is a more general way to formalize this problem, so that one could convincingly show that any hitting set for anything resembling "ZPP circuits" is just a hitting set.

Answer 2

If you are happy with impying $P=RP$ (which implies $P = ZPP$) but not $P = BPP$, then there is the Stoquastic PCP conjecture (or its classical version, a SetCSP PCP conjecture).