We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP).
We obtain new circuit lower bounds, as well as some hardness results for the relativized version of MCSP under randomized reductions. For example, we show that
\[
\ZPEXP^{\MCSP}\not\subseteq\P/\poly,
\]
and that
\[
\oplus\P\subseteq \ZPP^{\MCSP^{\oplus\P}}.
\]
Our results build on the recent work of Carmosino, Impagliazzo, Kabanets, and Kolokolova (CCC, 2016) connecting natural properties and learning algorithms.