The Power of Natural Properties as Oracles

Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich


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.