{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:41:26Z","timestamp":1764783686979},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,10,31]],"date-time":"2014-10-31T00:00:00Z","timestamp":1414713600000},"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,3]]},"DOI":"10.1007\/s00037-014-0095-y","type":"journal-article","created":{"date-parts":[[2014,10,30]],"date-time":"2014-10-30T09:18:59Z","timestamp":1414660739000},"page":"79-118","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games"],"prefix":"10.1007","volume":"26","author":[{"given":"Bar\u0131\u015f","family":"Ayd\u0131nl\u0131o\u011flu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dieter","family":"van Melkebeek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,10,31]]},"reference":[{"key":"95_CR1","doi-asserted-by":"crossref","unstructured":"Scott Aaronson & Dieter van Melkebeek (2011). On circuit lower bounds from derandomization. Theory of Computing 7, 177\u2013184.","DOI":"10.4086\/toc.2011.v007a012"},{"key":"95_CR2","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora & Boaz Barak (2009). Computational Complexity: A Modern Approach. Cambridge University Press.","DOI":"10.1017\/CBO9780511804090"},{"key":"95_CR3","doi-asserted-by":"crossref","unstructured":"Bar\u0131\u015f Ayd\u0131nl\u0131o\u011flu, Dan Gutfreund, John M. Hitchcock & Akinori Kawachi (2011). Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds. Computational Complexity 20(2), 329\u2013366.","DOI":"10.1007\/s00037-011-0010-8"},{"key":"95_CR4","doi-asserted-by":"crossref","unstructured":"Bar\u0131\u015f Ayd\u0131nl\u0131o\u011flu & Dieter van Melkebeek (2012). Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games. In Proceedings of the IEEE Conference on Computational Complexity, 269\u2013279.","DOI":"10.1109\/CCC.2012.32"},{"key":"95_CR5","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai, Lance Fortnow, Noam Nisan & Avi Wigderson (1993). BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs. Computational Complexity 3, 307\u2013318.","DOI":"10.1007\/BF01275486"},{"key":"95_CR6","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai & Shlomo Moran (1988). Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences 36(2), 254\u2013276.","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"95_CR7","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra & Mitsunori Ogihara (2005). Competing provers yield improved Karp-Lipton collapse results. Information and Computation 198(1), 1\u201323.","DOI":"10.1016\/j.ic.2005.01.002"},{"key":"95_CR8","doi-asserted-by":"crossref","unstructured":"Venkatesan T. Chakaravarthy & Sambuddha Roy (2011). Arthur and Merlin as oracles. Computational Complexity 20(3), 505\u2013558.","DOI":"10.1007\/s00037-011-0015-3"},{"key":"95_CR9","doi-asserted-by":"crossref","unstructured":"Oded Goldreich (2006). On Promise Problems: A Survey. In Essays in Memory of Shimon Even, 254\u2013290.","DOI":"10.1007\/11685654_12"},{"key":"95_CR10","doi-asserted-by":"crossref","unstructured":"Oded Goldreich (2011a). In a World of P=BPP. In Studies in Complexity and Cryptography, 191\u2013232.","DOI":"10.1007\/978-3-642-22670-0_20"},{"key":"95_CR11","unstructured":"Oded Goldreich (2011b). Two Comments on Targeted Canonical Derandomizers. Technical Report TR11-047, Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"95_CR12","doi-asserted-by":"crossref","unstructured":"Shafi Goldwasser & Michael Sipser (1986). Private Coins versus Public Coins in Interactive Proof Systems. In Proceedings of the ACM Symposium on Theory of Computing (STOC), 59\u201368.","DOI":"10.1145\/12130.12137"},{"key":"95_CR13","doi-asserted-by":"crossref","unstructured":"Dan Gutfreund, Ronen Shaltiel & Amnon Ta-Shma (2003). Uniform hardness versus randomness tradeoffs for Arthur-Merlin games. Computational Complexity 12(3-4), 85\u2013130.","DOI":"10.1007\/s00037-003-0178-7"},{"key":"95_CR14","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo, Valentine Kabanets & Avi Wigderson (2002). In search of an easy witness: exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences 65(4), 672\u2013694.","DOI":"10.1016\/S0022-0000(02)00024-7"},{"key":"95_CR15","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo & Avi Wigderson (1997). P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. In Proceedings of the ACM Symposium on Theory of Computing (STOC), 220\u2013229.","DOI":"10.1145\/258533.258590"},{"key":"95_CR16","doi-asserted-by":"crossref","unstructured":"Valentine Kabanets & Russell Impagliazzo (2004). Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity 13(1\/2), 1\u201346.","DOI":"10.1007\/s00037-004-0182-6"},{"key":"95_CR17","doi-asserted-by":"crossref","unstructured":"Ravi Kannan (1982). Circuit-size lower bounds and nonreducibility to sparse sets. Information and Control 55(1), 40\u201356.","DOI":"10.1016\/S0019-9958(82)90382-5"},{"key":"95_CR18","unstructured":"Richard M. Karp & Richard J. Lipton (1982). Turing machines that take advice. L\u2019Enseignement Math\u00e9matique 28(2), 191\u2013209."},{"key":"95_CR19","doi-asserted-by":"crossref","unstructured":"Jeff Kinne, Dieter van Melkebeek & Ronen Shaltiel (2012). Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds. Computational Complexity 21(1), 3\u201361.","DOI":"10.1007\/s00037-011-0019-z"},{"key":"95_CR20","doi-asserted-by":"crossref","unstructured":"Adam Klivans & Dieter van Melkebeek (2002). Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. SIAM Journal on Computing 31(5), 1501\u20131526.","DOI":"10.1137\/S0097539700389652"},{"key":"95_CR21","doi-asserted-by":"crossref","unstructured":"Carsten Lund, Lance Fortnow, Howard J. Karloff & Noam Nisan (1992). Algebraic Methods for Interactive Proof Systems. Journal of the ACM 39(4), 859\u2013868.","DOI":"10.1145\/146585.146605"},{"key":"95_CR22","doi-asserted-by":"crossref","unstructured":"Noam Nisan & Avi Wigderson (1994). Hardness vs. randomness. Journal of Computer and System Sciences 49(2), 149\u2013167.","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"95_CR23","doi-asserted-by":"crossref","unstructured":"Uwe Sch\u00f6ning (1989). Probabilistic complexity classes and lowness. Journal of Computer and System Sciences 39(1), 84\u2013100.","DOI":"10.1016\/0022-0000(89)90020-2"},{"key":"95_CR24","doi-asserted-by":"crossref","unstructured":"Ronen Shaltiel & Christopher Umans (2006). Pseudorandomness for Approximate Counting and Sampling. Computational Complexity 15(4), 298\u2013341.","DOI":"10.1007\/s00037-007-0218-9"},{"key":"95_CR25","doi-asserted-by":"crossref","unstructured":"Adi Shamir (1992). IP = PSPACE. Journal of the ACM 394), 869\u2013877","DOI":"10.1145\/146585.146609"},{"key":"95_CR26","unstructured":"Andrew Chi-Chih Yao (1982). Theory and Applications of Trapdoor Functions (Extended Abstract). In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), 80\u201391."},{"key":"95_CR27","doi-asserted-by":"crossref","unstructured":"Chee-Keng Yap (1983). Some Consequences of Non-Uniform Conditions on Uniform Classes. Theoretical Computer Science 26, 287\u2013300.","DOI":"10.1016\/0304-3975(83)90020-8"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-014-0095-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-014-0095-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-014-0095-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-014-0095-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T16:52:48Z","timestamp":1565974368000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-014-0095-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,31]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["95"],"URL":"https:\/\/doi.org\/10.1007\/s00037-014-0095-y","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,31]]}}}