Theory Seminar

The Power of Natural Properties as Oracles

Ilya Volkovich

Friday, October 05, 2018
10:00am - 11:00am
BBB 3941

Add to Google Calendar

About the Event

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 show that in a number of complexity-theoretic results that use the SAT oracle, one can use the MCSP oracle instead. For example, we show that ZPEXP^MCSP \not \subseteq P/poly, which should be contrasted with the previously known circuit lower bound ZPEXP^NP \not \subseteq P/poly. We also show that, assuming the existence of Indistinguishability Obfuscators (IO), SAT and MCSP are equivalent in the sense that one has a ZPP algorithm if and only the other one does. We interpret our results as providing some evidence that MCSP may be NP-hard under randomized polynomial-time reductions. Joint work with Russell Impagliazzo and Valentine Kabanets.

Additional Information

Sponsor(s): Theory Group

Faculty Sponsor: Seth Pettie

Open to: Public