We prove new results regarding the complexity of various complexity classes under randomized oracle reductions. We first prove that BPPprSZKAMcoAM, where prSZK is the class of promise problems having statistical zero knowledge proofs. This strengthens the previously known facts that \prSZK is closed under NC1 truth-table reductions (Sahai and Vadhan, J. ACM '03) and that PprSZKAMcoAM (Vadhan, personal communication). Our results imply that for most cryptographically interesting lattice problems, there is a sharp threshold for the approximation factor below which we do not know if the problems are even in AM, while above which the problems are in AMcoAM not only via Karp reductions but also via randomized oracle reductions.

Then we investigate the power of randomized oracle reductions with relation to the notion of instance checking (Blum and Kannan, J. ACM '95). We observe that a theorem of Beigel implies that if any problem in TFNP such as Nash equilibrium is NP-hard under randomized oracle reductions, then SAT is checkable.

We also observe that Beigel's theorem can be extended to an average-case setting by relating checking to the notion of program testing (Blum et al., JCSS '93). From this, we derive that if one-way functions can be based on NP-hardness via a randomized oracle reduction, then SAT is checkable. By showing that NP has a \emph{non-uniform} tester, we also show that worst-case to average-case randomized oracle reduction for any relation (or language) RNP implies that R has a non-uniform instance checker. These results hold even for adaptive randomized oracle reductions.