{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:46:45Z","timestamp":1781030805453,"version":"3.54.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,2,17]],"date-time":"2016-02-17T00:00:00Z","timestamp":1455667200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1007\/s00037-016-0124-0","type":"journal-article","created":{"date-parts":[[2016,2,17]],"date-time":"2016-02-17T03:42:01Z","timestamp":1455680521000},"page":"469-496","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["The Minimum Oracle Circuit Size Problem"],"prefix":"10.1007","volume":"26","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dhiraj","family":"Holden","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Valentine","family":"Kabanets","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,2,17]]},"reference":[{"issue":"1","key":"124_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.jcss.2010.06.003","volume":"77","author":"Agrawal Manindra","year":"2011","unstructured":"Manindra Agrawal (2011) The isomorphism conjecture for constant depth reductions. Journal of Computer and System Sciences 77(1): 3\u201313","journal-title":"Journal of Computer and System Sciences"},{"key":"124_CR2","unstructured":"Manindra Agrawal (2014). Personal Communication."},{"key":"124_CR3","doi-asserted-by":"publisher","unstructured":"Eric Allender, Harry Buhrman, Michal Kouck\u1ef3, Dieter van Melkebeek & Detlef Ronneburger (2006). Power from random strings. SIAM Journal on Computing 35(6), 1467\u20131493.","DOI":"10.1137\/050628994"},{"key":"124_CR4","doi-asserted-by":"publisher","unstructured":"Eric Allender & Bireswar Das (2014). Zero Knowledge and Circuit Minimization. In Mathematical Foundations of Computer Science (MFCS), volume 8635 of Lecture Notes in Computer Science, 25\u201332. Springer.","DOI":"10.1007\/978-3-662-44465-8_3"},{"issue":"2","key":"124_CR5","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0020-0190(91)90015-A","volume":"40","author":"Allender Eric","year":"1991","unstructured":"Eric Allender, Vivek Gore (1991) Rudimentary Reductions Revisited. Information Processing Letters 40(2): 89\u201395","journal-title":"Information Processing Letters"},{"key":"124_CR6","unstructured":"Eric Allender & Vivek Gore (1993). On strong separations from AC0. In Advances in Computational Complexity Theory, Jin-Yi Cai, editor, volume 13 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 21\u201337. AMS Press."},{"key":"124_CR7","unstructured":"Eric Allender, Dhiraj Holden & Valentine Kabanets (2015). The Minimum Oracle Circuit Size Problem. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, Ernst W. Mayr & Nicolas Ollinger, editors, volume 30 of LIPIcs, 21\u201333. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. ISBN 978-3-939897-78-1. \n                        http:\/\/dx.doi.org\/10.4230\/LIPIcs.STACS.2015.21\n                        \n                    ."},{"key":"124_CR8","doi-asserted-by":"publisher","unstructured":"Eric Allender, Michal Kouck\u00fd, Detlef Ronneburger & Sambuddha Roy (2010). The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. Journal of Computer and System Sciences 77, 14\u201340.","DOI":"10.1016\/j.jcss.2010.06.004"},{"key":"124_CR9","doi-asserted-by":"publisher","unstructured":"Jos\u00e9 L Balc\u00e1zar, Antoni Lozano & Jacobo Tor\u00e1n (1992). The complexity of algorithmic problems on succinct instances. In Computer Science, 351\u2013377. Springer.","DOI":"10.1007\/978-1-4615-3422-8_30"},{"key":"124_CR10","doi-asserted-by":"publisher","unstructured":"Stephen A. Fenner, Lance Fortnow & Stuart A. Kurtz (1994). Gap-Definable Counting Classes. Journal of Computer and System Sciences\n                     48(1), 116\u2013148.","DOI":"10.1016\/S0022-0000(05)80024-8"},{"issue":"2","key":"124_CR11","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1006\/jcss.1999.1671","volume":"60","author":"Fortnow Lance","year":"2000","unstructured":"Lance Fortnow (2000) Time-Space Tradeoffs for Satisfiability. Journal of Computer and System Sciences 60(2): 337\u2013353","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"124_CR12","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"Galperin Hana","year":"1983","unstructured":"Hana Galperin, Avi Wigderson (1983) Succinct representations of graphs. Information and Control 56(3): 183\u2013198","journal-title":"Information and Control"},{"key":"124_CR13","doi-asserted-by":"publisher","unstructured":"Oded Goldreich, Amit Sahai & Salil Vadhan (1998). Honest-verifier statistical zero-knowledge equals general statistical zero-knowledge. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, 399\u2013408. ACM.","DOI":"10.1145\/276698.276852"},{"key":"124_CR14","unstructured":"Johan H\u00e5stad (1989). Almost optimal lower bounds for small depth circuits. In Randomness and Computation, S. Micali, editor, 143\u2013170. Advances in Computing Research, vol. 5, JAI Press, Greenwich, Connecticut."},{"key":"124_CR15","doi-asserted-by":"publisher","unstructured":"Valentine Kabanets & Jin-Yi Cai (2000). Circuit minimization problem. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, 73\u201379. ACM.","DOI":"10.1145\/335305.335314"},{"key":"124_CR16","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0019-9958(84)80060-1","volume":"61","author":"Levin Leonid","year":"1984","unstructured":"Leonid Levin (1984) Randomness Conservation Inequalities; Information and Independence in Mathematical Theories. Inf. and Control 61: 15\u201337","journal-title":"Inf. and Control"},{"issue":"7","key":"124_CR17","doi-asserted-by":"publisher","first-page":"3186","DOI":"10.1137\/080741811","volume":"39","author":"McKenzie Pierre","year":"2010","unstructured":"Pierre McKenzie, Michael Thomas, Heribert Vollmer (2010) Extensional uniformity for boolean circuits. SIAM Journal on Computing 39(7): 3186\u20133206","journal-title":"SIAM Journal on Computing"},{"key":"124_CR18","unstructured":"Cody Murray & Ryan Williams (2015). On the (Non) NP-Hardness of Computing Circuit Complexity. In 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA, volume 33 of LIPIcs, 365\u2013380. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. \n                        http:\/\/dx.doi.org\/10.4230\/LIPIcs.CCC.2015.365\n                        \n                    ."},{"issue":"1","key":"124_CR19","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1006\/jcss.1999.1664","volume":"60","author":"Okamoto Tatsuaki","year":"2000","unstructured":"Tatsuaki Okamoto (2000) On Relationships between Statistical Zero-Knowledge Proofs. Journal of Computer and System Sciences 60(1): 47\u2013108","journal-title":"Journal of Computer and System Sciences"},{"key":"124_CR20","unstructured":"Christos H. Papadimitriou (2003). Computational complexity. John Wiley and Sons Ltd."},{"key":"124_CR21","doi-asserted-by":"publisher","unstructured":"Christos H. Papadimitriou & Mihalis Yannakakis (1986). A note on succinct representations of graphs. Information and Control 71(3), 181\u2013185.","DOI":"10.1016\/S0019-9958(86)80009-2"},{"key":"124_CR22","doi-asserted-by":"publisher","unstructured":"Joel I. Seiferas, Michael J. Fischer & Albert R. Meyer (1978). Separating Nondeterministic Time Complexity Classes. J. ACM\n                     25(1), 146\u2013167.","DOI":"10.1145\/322047.322061"},{"key":"124_CR23","unstructured":"Raymond M. Smullyan (1961). Theory of Formal systems. In Annals of Math. Studies 47. Princeton University Press."},{"issue":"5","key":"124_CR24","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"Toda Seinosuke","year":"1991","unstructured":"Seinosuke Toda (1991) PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing 20(5): 865\u2013877","journal-title":"SIAM Journal on Computing"},{"key":"124_CR25","doi-asserted-by":"publisher","unstructured":"Jacobo Tor\u00e1n (1991). Complexity classes defined by counting quantifiers. J. ACM\n                     38(3), 752\u2013773.","DOI":"10.1145\/116825.116858"},{"key":"124_CR26","doi-asserted-by":"publisher","unstructured":"Boris A. Trakhtenbrot (1984). A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms. IEEE Annals of the History of Computing\n                     6(4), 384\u2013400.","DOI":"10.1109\/MAHC.1984.10036"},{"key":"124_CR27","doi-asserted-by":"publisher","unstructured":"Klaus W. Wagner (1986). The complexity of combinatorial problems with succinct input representation. Acta Informatica\n                     23(3), 325\u2013356.","DOI":"10.1007\/BF00289117"},{"key":"124_CR28","unstructured":"Ryan Williams (2012). \n                        http:\/\/cstheory.stackexchange.com\/questions\/10320\/succinct-problems-in-mathsfp\/10546#10546\n                        \n                    ."},{"issue":"2","key":"124_CR29","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1137\/0207018","volume":"7","author":"Wrathall Celia","year":"1978","unstructured":"Celia Wrathall (1978) Rudimentary predicates and relative computation. SIAM Journal on Computing 7(2): 194\u2013209","journal-title":"SIAM Journal on Computing"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0124-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0124-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0124-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0124-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T11:01:59Z","timestamp":1558522919000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0124-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,17]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["124"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0124-0","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,17]]}}}