Two queries related to Toda

Question

Is the Isolation lemma crucial for $PH\subseteq BPP^{\oplus P}$ theorem and would avoiding the Isolation lemma say anything more that is not known?

Answer 1

Re 1: It seems unlikely to me that the Isolation Lemma is necessary for $\mathsf{PH} \subseteq \mathsf{BPP}^{\mathsf{\oplus P}}$. For example, even for $\mathsf{NP} \subseteq \mathsf{BPP}^{\mathsf{\oplus P}}$ you don't need to isolate a witness, you just need to make their cardinality odd. That being said, I think the only known proof of $\mathsf{NP} \subseteq \mathsf{BPP}^{\mathsf{\oplus P}}$ goes through Valiant-Vazirani. (But proving that Valiant-Vazirani is necessary for $\mathsf{NP} \subseteq \mathsf{BPP}^{\mathsf{\oplus P}}$ - that is, that $\mathsf{NP} \subseteq \mathsf{BPP}^{\mathsf{\oplus P}} \Rightarrow \mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$ - also seems hard, if not false.)

Now, if you ask if the isolation lemma is necessary for the Valiant-Vazirani Theorem ($\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$), this seems more plausible - since you're reducing from many witnesses to a unique witness - but still hard to prove. To actually prove this, you'd want to prove that just based on the assumption $\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$ that you get some version of an isolation lemma. The reason I say this seems hard to prove is as follows. Suppose you wanted to prove this. Then you'd take, say, SAT and try to show that you can isolate witnesses. The issue is that all you know from the assumption is that there is some randomized poly-time oracle machine $M$ with one-sided error, and some oracle in $\mathcal{O} \in \mathsf{PromiseUP}$ such that $SAT = L(M^\mathcal{O})$. But nothing in this assumption says that the witnesses for the $\mathcal{O}$ oracle are in any way related to the satisfying assignments for SAT (other than that $SAT = L(M^\mathcal{O})$). Even if you could somehow show such a relationship, you still don't know that the machine $M$ produces oracle queries such that the witnesses for those queries are related to the witnesses to the original SAT assignments. Nonetheless, philosophically it at least seems plausible to me that $\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$ is equivalent to the isolation lemma.

The question of whether the isolation lemma is necessary for the Valiant-Vazirani Theorem - and the issue I raised in the preceding paragraph - are closely related to the difference between, say, $\mathsf{NP} = \mathsf{UP}$ and $\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$. The latter essentially says that you can indeed isolate witnesses, at least nondeterministically. I suppose the isolation lemma itself can be formalized in terms of complexity classes as $\mathsf{NPMV} \subseteq_c \mathsf{RPSV}$.