{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:44:57Z","timestamp":1740109497036,"version":"3.37.3"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,7,6]],"date-time":"2023-07-06T00:00:00Z","timestamp":1688601600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,7,6]],"date-time":"2023-07-06T00:00:00Z","timestamp":1688601600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2023,12]]},"DOI":"10.1007\/s00037-023-00241-0","type":"journal-article","created":{"date-parts":[[2023,7,6]],"date-time":"2023-07-06T09:02:26Z","timestamp":1688634146000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The Power of Natural Properties as Oracles"],"prefix":"10.1007","volume":"32","author":[{"given":"Russell","family":"Impagliazzo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valentine","family":"Kabanets","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilya","family":"Volkovich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,6]]},"reference":[{"key":"241_CR1","doi-asserted-by":"crossref","unstructured":"L. M. Adleman (1978). Two Theorems on Random Polynomial Time.\nIn Proceedings of the 19th Annual IEEE Symposium on Foundations of\nComputer Science (FOCS), 75\u201383.","DOI":"10.1109\/SFCS.1978.37"},{"key":"241_CR2","doi-asserted-by":"crossref","unstructured":"E. Allender, H. Buhrman, M.l Kouck\u00fd, D. van Melkebeek &\nD. Ronneburger (2006). Power from Random Strings. SIAM J. Comput.\n35(6), 1467\u20131493. URL http:\/\/dx.doi.org\/10.1137\/050628994.","DOI":"10.1137\/050628994"},{"key":"241_CR3","doi-asserted-by":"crossref","unstructured":"E. Allender & B. Das (2014). Zero Knowledge and Circuit Minimization.\nIn Mathematical Foundations of Computer Scienc MFCS,\n25\u201332.","DOI":"10.1007\/978-3-662-44465-8_3"},{"key":"241_CR4","doi-asserted-by":"crossref","unstructured":"E. Allender, L. Hellerstein, P. McCabe, T. Pitassi & M. E.\nSaks (2008). Minimizing Disjunctive Normal Form Formulas and AC0\nCircuits Given a Truth Table. SIAM J. Comput. 38(1), 63\u201384. URL\nhttp:\/\/dx.doi.org\/10.1137\/060664537.","DOI":"10.1137\/060664537"},{"key":"241_CR5","unstructured":"E. Allender, D. Holden & V. Kabanets (2015). The Minimum\nOracle Circuit Size Problem. In 32nd International Symposium on\nTheoretical Aspects of Computer Science, STACS 2015, March 4-7,\n2015, Garching, Germany, 21\u201333. URL http:\/\/dx.doi.org\/10.4230\/LIPIcs.STACS.2015.21."},{"key":"241_CR6","doi-asserted-by":"crossref","unstructured":"S. Arora & B. Barak (2009). Computational complexity: a modern\napproach. Cambridge University Press.","DOI":"10.1017\/CBO9780511804090"},{"key":"241_CR7","doi-asserted-by":"crossref","unstructured":"V. Arvind & J. K\u00f6bler (2001). On pseudorandomness and resourcebounded\nmeasure. Theor. Comput. Sci. 255(1-2), 205\u2013221.","DOI":"10.1016\/S0304-3975(99)00164-4"},{"key":"241_CR8","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow & C. Lund (1991). Non-Deterministic Exponential\nTime Has Two-Prover Interactive Protocols. Computational\nComplexity 1, 3\u201340.","DOI":"10.1007\/BF01200056"},{"key":"241_CR9","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, N. Nisan & A. Wigderson (1993). BPP\nhas subexponential time simulations unless EXPTIME has publishable\nproofs. Computational Complexity 3, 307\u2013318.","DOI":"10.1007\/BF01275486"},{"key":"241_CR10","doi-asserted-by":"crossref","unstructured":"B. Barak (2002). A Probabilistic-Time Hierarchy Theorem for\n\u201dSlightly Non-uniform\u201d Algorithms. In RANDOM, 194\u2013208.","DOI":"10.1007\/3-540-45726-7_16"},{"key":"241_CR11","doi-asserted-by":"crossref","unstructured":"B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai,\nS. P. Vadhan & K. Yang (2001). On the (Im)possibility of Obfuscating\nPrograms. In Advances in Cryptology - CRYPTO 2001, 21st\nAnnual International Cryptology Conference, 1\u201318.","DOI":"10.1007\/3-540-44647-8_1"},{"key":"241_CR12","doi-asserted-by":"crossref","unstructured":"D. Beaver & J. Feigenbaum (1990). Hiding Instances in Multioracle\nQueries. In STACS, 37\u201348. URL http:\/\/dx.doi.org\/10.1007\/3-540-52282-4_30.","DOI":"10.1007\/3-540-52282-4_30"},{"key":"241_CR13","doi-asserted-by":"crossref","unstructured":"N. H. Bshouty, R. Cleve, R. Gavald\u00e0, S. Kannan & C. Tamon\n(1996). Oracles and Queries That Are Sufficient for Exact Learning. J.\nComput. Syst. Sci. 52(3), 421\u2013433.","DOI":"10.1006\/jcss.1996.0032"},{"key":"241_CR14","doi-asserted-by":"crossref","unstructured":"H. Buhrman, L. Fortnow & T. Thierauf (1998). Nonrelativizing\nSeparations. In Proceedings of the 13th Annual IEEE Conference on\nComputational Complexity (CCC), 8\u201312.","DOI":"10.1109\/CCC.1998.694585"},{"key":"241_CR15","doi-asserted-by":"crossref","unstructured":"H. Buhrman & S. Homer (1992). Superpolynomial Circuits, Almost\nSparse Oracles and the Exponential Hierarchy. In Foundations of Software\nTechnology and Theoretical Computer Science, 12th Conference,\nNew Delhi, India, December 18-20, 1992, Proceedings, 116\u2013127. URL\nhttp:\/\/dx.doi.org\/10.1007\/3-540-56287-7_99.","DOI":"10.1007\/3-540-56287-7_99"},{"key":"241_CR16","unstructured":"M. L. Carmosino, R. Impagliazzo, V. Kabanets &\nA. Kolokolova (2016). Learning Algorithms from Natural Proofs.\nIn Proceedings of the 31st Conference on Computational Complexity,\nCCC, 1\u201324."},{"key":"241_CR17","doi-asserted-by":"crossref","unstructured":"J. Feigenbaum & L. Fortnow (1993). Random-self-reducibility of\ncomplete sets. SIAM J. on Computing 22(5), 994\u20131005. ISSN 0097-5397.","DOI":"10.1137\/0222061"},{"key":"241_CR18","doi-asserted-by":"crossref","unstructured":"L. Fortnow & A. R. Klivans (2009). Efficient learning algorithms\nyield circuit lower bounds. J. Comput. Syst. Sci. 75(1), 27\u201336.","DOI":"10.1016\/j.jcss.2008.07.006"},{"key":"241_CR19","unstructured":"L. Fortnow & R. Santhanam (2004). Hierarchy Theorems for Probabilistic\nPolynomial Time. In Proceedings of the 45th Annual IEEE\nSymposium on Foundations of Computer Science (FOCS), 316\u2013324."},{"key":"241_CR20","doi-asserted-by":"crossref","unstructured":"O. Goldreich & D. Zuckerman (2011). Another Proof That BPP\n$$\\subseteq$$ PH (and More). Studies in Complexity and Cryptography 40\u201353.","DOI":"10.1007\/978-3-642-22670-0_6"},{"key":"241_CR21","doi-asserted-by":"crossref","unstructured":"S. Goldwasser & G. N. Rothblum (2014). On Best-Possible Obfuscation.\nJ. Cryptol. 27(3), 480\u2013505. URL https:\/\/doi.org\/10.1007\/s00145-013-9151-z.","DOI":"10.1007\/s00145-013-9151-z"},{"key":"241_CR22","doi-asserted-by":"crossref","unstructured":"H. Heller (1986). On Relativized Exponential and Probabilistic Complexity\nClasses. Information and Control 71(3), 231\u2013243. URL http:\/\/dx.doi.org\/10.1016\/S0019-9958(86)80012-2.","DOI":"10.1016\/S0019-9958(86)80012-2"},{"key":"241_CR23","unstructured":"Sh. Hirahara & O. Watanabe (2016). Limits of Minimum Circuit\nSize Problem as Oracle. In 31st Conference on Computational Complexity,\nCCC, 18:1\u201318:20. URL http:\/\/dx.doi.org\/10.4230\/LIPIcs.CCC.2016.18."},{"key":"241_CR24","unstructured":"J. M. Hitchcock & A. Pavan (2015). On the NP-Completeness of\nthe Minimum Circuit Size Problem. In 35th IARCS Annual Conference\non Foundation of Software Technology and Theoretical Computer Science,\nFSTTCS, 236\u2013245. URL http:\/\/dx.doi.org\/10.4230\/LIPIcs.FSTTCS.2015.236."},{"key":"241_CR25","unstructured":"R. Ilango (2020a). Approaching MCSP from Above and Below: Hardness\nfor a Conditional Variant and AC\u02c60[p]. In 11th Innovations in\nTheoretical Computer Science Conference, ITCS, volume 151 of LIPIcs,\n34:1\u201334:26. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. URL\nhttps:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2020.34."},{"key":"241_CR26","doi-asserted-by":"crossref","unstructured":"R. Ilango (2020b). Constant Depth Formula and Partial Function\nVersions of MCSP are Hard. In 61st IEEE Annual Symposium on Foundations\nof Computer Science, FOCS, 424\u2013433. IEEE.","DOI":"10.1109\/FOCS46700.2020.00047"},{"key":"241_CR27","unstructured":"R. Ilango, B. Loff & I. Carboni Oliveira (2020). NP-Hardness of\nCircuit Minimization for Multi-Output Functions. In 35th Conference\non Computational Complexity, CCC, volume 169 of LIPIcs, 22:1\u201322:36.\nSchloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik."},{"key":"241_CR28","unstructured":"R. Impagliazzo, V. Kabanets & I. Volkovich (2018). The Power\nof Natural Properties as Oracles. In 33rd Computational Complexity\nConference CCC, 7:1\u20137:20. URL https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2018.7."},{"key":"241_CR29","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, V. Kabanets & A. Wigderson (2002). In search\nof an easy witness: exponential time vs. probabilistic polynomial time.\nJ. of Computer and System Sciences 65(4), 672\u2013694.","DOI":"10.1016\/S0022-0000(02)00024-7"},{"key":"241_CR30","unstructured":"R. Impagliazzo & A. Wigderson (1997). P=BPP unless E has\nsubexponential circuits: derandomizing the XOR lemma. In Proceedings\nof the 29th Annual ACM Symposium on Theory of Computing (STOC),\n220\u2013229."},{"key":"241_CR31","unstructured":"R. Impagliazzo & A. Wigderson (1998). Randomness vs. Time:\nDe-Randomization under a Uniform Assumption. In Proceedings of the\n39th Annual IEEE Symposium on Foundations of Computer Science\n(FOCS), 734\u2013743."},{"key":"241_CR32","doi-asserted-by":"crossref","unstructured":"A. Jain, H. Lin & A. Sahai (2021). Indistinguishability obfuscation\nfrom well-founded assumptions. In 53rd Annual ACM SIGACT Symposium\non Theory of Computing, STOC, 60\u201373. ACM. URL https:\/\/doi.org\/10.1145\/3406325.3451093.","DOI":"10.1145\/3406325.3451093"},{"key":"241_CR33","doi-asserted-by":"crossref","unstructured":"V. Kabanets & J. Cai (2000). Circuit minimization problem. In Proceedings\nof the 32nd Annual ACM Symposium on Theory of Computing\n(STOC), 73\u201379.","DOI":"10.1145\/335305.335314"},{"key":"241_CR34","doi-asserted-by":"crossref","unstructured":"R. M. Karp (1985). Turing award lecture. In Proceedings of the\n1985 ACM annual conference on The range of computing: mid-80\u2019s\nperspective: mid-80\u2019s perspective, Denver, Colorado, USA, October 14-16, 1985, 193.","DOI":"10.1145\/320435.320497"},{"key":"241_CR35","unstructured":"R. M. Karp & R. J. Lipton (1980). Some Connections between\nNonuniform and Uniform Complexity Classes. In Proceedings of the\n12th Annual ACM Symposium on Theory of Computing, April 28-30,\n1980, Los Angeles, California, USA, 302\u2013309. URL http:\/\/doi.acm.org\/10.1145\/800141.804678."},{"key":"241_CR36","doi-asserted-by":"crossref","unstructured":"A. Klivans, P. Kothari & I. Oliveira (2013). Constructing Hard\nFunctions from Learning Algorithms. In Proceedings of the 28th Annual\nIEEE Conference on Computational Complexity (CCC), 86\u201397.","DOI":"10.1109\/CCC.2013.18"},{"key":"241_CR37","doi-asserted-by":"crossref","unstructured":"Adam Klivans & Dieter van Melkebeek (2002). Graph Nonisomorphism\nHas Subexponential Size Proofs Unless the Polynomial-\nTime Hierarchy Collapses. SIAM J. Comput. 31(5), 1501\u20131526. URL\nhttp:\/\/dx.doi.org\/10.1137\/S0097539700389652.","DOI":"10.1137\/S0097539700389652"},{"key":"241_CR38","doi-asserted-by":"crossref","unstructured":"J. K\u00f6bler & O. Watanabe (1998). New Collapse Consequences of\nNP Having Small Circuits. SIAM J. Comput. 28(1), 311\u2013324.","DOI":"10.1137\/S0097539795296206"},{"key":"241_CR39","doi-asserted-by":"crossref","unstructured":"C. Lund, L. Fortnow, H. Karloff & N. Nisan (1992). Algebraic\nmethods for interactive proof systems. JACM 39(4), 859\u2013868.","DOI":"10.1145\/146585.146605"},{"key":"241_CR40","doi-asserted-by":"crossref","unstructured":"D. van Melkebeek & K. Pervyshev (2007). A Generic Time Hierarchy\nwith One Bit of Advice. Computational Complexity 16(2), 139\u2013179.","DOI":"10.1007\/s00037-007-0227-8"},{"key":"241_CR41","unstructured":"C. D. Murray & R. R. Williams (2015). On the (Non) NP-Hardness\nof Computing Circuit Complexity. In 30th Conference on Computational\nComplexity, CCC, 365\u2013380. URL http:\/\/dx.doi.org\/10.4230\/LIPIcs.CCC.2015.365."},{"key":"241_CR42","doi-asserted-by":"crossref","unstructured":"N. Nisan & A. Wigderson (1994). Hardness vs. randomness. J.\nComput. Syst. Sci. 49(2), 149\u2013167. ISSN 0022-0000.","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"241_CR43","unstructured":"I. C. Oliveira & R. Santhanam (2017). Conspiracies Between Learning\nAlgorithms, Circuit Lower Bounds, and Pseudorandomness. In 32nd\nComputational Complexity Conference, CCC, 18:1\u201318:49."},{"key":"241_CR44","doi-asserted-by":"crossref","unstructured":"A. A. Razborov & S. Rudich (1997). Natural Proofs. J. of Computer\nand System Sciences 55(1), 24\u201335.","DOI":"10.1006\/jcss.1997.1494"},{"key":"241_CR45","unstructured":"M. Saks & R. Santhanam (2020). Circuit Lower Bounds from NPHardness\nof MCSP Under Turing Reductions. In 35th Computational\nComplexity Conference, CCC, 26:1\u201326:13."},{"key":"241_CR46","doi-asserted-by":"crossref","unstructured":"R. Santhanam (2009). Circuit Lower Bounds for Merlin\u2013Arthur\nClasses. SIAM J. Comput. 39(3), 1038\u20131061.","DOI":"10.1137\/070702680"},{"key":"241_CR47","doi-asserted-by":"crossref","unstructured":"S. Toda (1991). PP is as hard as the polynomial time hierarchy. SIAM\nJ. on Computing 20(5), 865\u2013877.","DOI":"10.1137\/0220053"},{"key":"241_CR48","doi-asserted-by":"crossref","unstructured":"B. A. Trakhtenbrot (1984). A Survey of Russian Approaches to\nPerebor (Brute-Force Searches) Algorithms. IEEE Annals of the History\nof Computing 6(4), 384\u2013400.","DOI":"10.1109\/MAHC.1984.10036"},{"key":"241_CR49","doi-asserted-by":"crossref","unstructured":"L. Trevisan & S. P. Vadhan (2007). Pseudorandomness and\nAverage-Case Complexity Via Uniform Reductions. Computational\nComplexity 16(4), 331\u2013364.","DOI":"10.1007\/s00037-007-0233-x"},{"key":"241_CR50","doi-asserted-by":"crossref","unstructured":"C. Umans (2003). Pseudo-random generators for all hardnesses. J. of\nComputer and System Sciences 67(2), 419\u2013440.","DOI":"10.1016\/S0022-0000(03)00046-1"},{"key":"241_CR51","doi-asserted-by":"crossref","unstructured":"L. G. Valiant (1979). The complexity of computing the permanent.\nTheoretical Computer Science 8(2), 189\u2013201. ISSN 0304-3975.","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"241_CR52","doi-asserted-by":"crossref","unstructured":"L. G. Valiant (1984). A theory of the learnable. Communications of\nthe ACM 27(11), 1134\u20131142.","DOI":"10.1145\/1968.1972"},{"key":"241_CR53","doi-asserted-by":"crossref","unstructured":"I. Volkovich (2014). On Learning, Lower Bounds and (un)Keeping\nPromises. In Proceedings of the 41st ICALP, 1027\u20131038.","DOI":"10.1007\/978-3-662-43948-7_85"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00241-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-023-00241-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00241-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,26]],"date-time":"2023-12-26T19:04:27Z","timestamp":1703617467000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-023-00241-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,6]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["241"],"URL":"https:\/\/doi.org\/10.1007\/s00037-023-00241-0","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2023,7,6]]},"assertion":[{"value":"11 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"6"}}