Name
Abstract | ||
|---|---|---|
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 subset of P/poly, which should be contrasted with the previously known circuit lower bound ZPEXP(NP) not subset of 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4230/LIPIcs.CCC.2018.7 | Leibniz International Proceedings in Informatics |
Keywords | DocType | Volume |
natural properties,Minimal Circuit Size Problem (MCSP),circuit lower bounds,hardness of MCSP,learning algorithms,obfuscation,Indistinguishability Obfuscators (IO) | Conference | 102 |
ISSN | Citations | PageRank |
1868-8969 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Russell Impagliazzo | 1 | 5444 | 482.13 |
| Valentine Kabanets | 2 | 562 | 35.38 |
| Ilya Volkovich | 3 | 145 | 8.64 |