{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:10:19Z","timestamp":1742598619447,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540590422"},{"type":"electronic","value":"9783540491750"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59042-0_111","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:00:01Z","timestamp":1330275601000},"page":"628-639","source":"Crossref","is-referenced-by-count":2,"title":["Malign distributions for average case circuit complexity"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Jakoby","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R\u00fcdiger","family":"Reischuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Schindelhauer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"55_CR1","first-page":"193","volume":"44","author":"S. Ben-David","year":"1992","unstructured":"S. Ben-David, B. Chor, O. Goldreich, M. Luby, On the Theory of Average Case Complexity, J. CSS 44, 1992, 193\u2013219.","journal-title":"J. CSS"},{"key":"55_CR2","doi-asserted-by":"crossref","unstructured":"B. Bollig, M. H\u00fchne, S. P\u00f6lt, P. Savick\u00fd, On the Average Case Circuit Delay of Disjunction, Technical Report, University of Dortmund, 1994.","DOI":"10.1142\/S0129626495000254"},{"key":"55_CR3","doi-asserted-by":"crossref","unstructured":"I. David, R. Ginosar, M. Yoelli, An Efficient Implementation of Boolean Functions and Finite State Machines as Self-Timed Circuits, ACM SIG-ARCH, 1989, 91\u2013104.","DOI":"10.1109\/EEIS.1989.720129"},{"key":"55_CR4","first-page":"265","volume":"34","author":"Gaskov","year":"1978","unstructured":"Gaskov, The Depth of Boolean Functions, Prob. Kybernet. 34, 1978, 265\u2013268.","journal-title":"Prob. Kybernet."},{"key":"55_CR5","doi-asserted-by":"crossref","unstructured":"P. Grape, Complete Problems with L-sampleable Distributions, Proc. 2. SWAT 90, 360\u2013367.","DOI":"10.1007\/3-540-52846-6_104"},{"key":"55_CR6","first-page":"346","volume":"42","author":"Y. Gurevich","year":"1991","unstructured":"Y. Gurevich Average Case Completeness, J. CSS 42, 1991, 346\u2013398.","journal-title":"J. CSS"},{"key":"55_CR7","doi-asserted-by":"crossref","unstructured":"A. Jakoby, R. Reischuk, C. Schindelhauer, Circuit Complexity: from the Worst Case to the Average Case, Proc. 26. STOC, 1994, 58\u201367.","DOI":"10.1145\/195058.195106"},{"key":"55_CR8","doi-asserted-by":"crossref","unstructured":"A. Jakoby, R. Reischuk, C. Schindelhauer, S. Weis The Average Case Complexity of the Parallel Prefix Problem, Proc. 21. ICALP, 1994, 593\u2013604.","DOI":"10.1007\/3-540-58201-0_101"},{"key":"55_CR9","first-page":"634","volume":"76","author":"K. Kobayashi","year":"1993","unstructured":"K. Kobayashi, On Malign Input Distributions for Algorithms, IEICE Trans. Inf. & Syst. 76, 1993, 634\u2013640.","journal-title":"IEICE Trans. Inf. & Syst."},{"key":"55_CR10","first-page":"1006","volume":"19","author":"V. Krapchenko","year":"1978","unstructured":"V. Krapchenko, Depth and Delay in a Network, Soviet Math. Dokl. 19, 1978, 1006\u20131009.","journal-title":"Soviet Math. Dokl."},{"key":"55_CR11","doi-asserted-by":"crossref","unstructured":"W. Lam, R. Brayton, A. Sangiovanni-Vincentelli, Circuit Delay Models and Their Exact Computation Using Timed Boolean Functions, ACM\/IEEE, Design Automation Conference, 1993, 128\u2013133.","DOI":"10.1145\/157485.164625"},{"key":"55_CR12","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L. Levin","year":"1986","unstructured":"L. Levin, Average Case Complete Problems, SIAM J. Computing 15, 1986, 285\u2013286.","journal-title":"SIAM J. Computing"},{"key":"55_CR13","doi-asserted-by":"crossref","unstructured":"M. Li, P. Vitanyi, Inductive Reasoning and Kolmogorov Complexity, Proc. 4. Structure, 1989, 165\u2013185.","DOI":"10.1109\/SCT.1989.41823"},{"key":"55_CR14","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0020-0190(92)90138-L","volume":"42","author":"M. Li","year":"1992","unstructured":"M. Li, P. Vitanyi, Average Case Complexity under the Universal Distribution Equals Worst-Case Complexity, IPL 42, 1992, 145\u2013149.","journal-title":"IPL"},{"key":"55_CR15","first-page":"164","volume":"22","author":"P. Miltersen","year":"1991","unstructured":"P. Miltersen, The Complexity of Malign Ensembles, Proc. 6. Structure in Complexity Theory, 1991, 164\u2013171, see also SIAM. J. Comput. 22, 1993, 147\u2013156.","journal-title":"J. Comput."},{"key":"55_CR16","doi-asserted-by":"crossref","unstructured":"R. Reischuk, C. Schindelhauer, Precise Average Case Complexity, Proc. 10. GI-AFCET Symposium on Theoretical Aspects of Computer Science, STACS 1993, Springer Lecture Notes, 650\u2013661.","DOI":"10.1007\/3-540-56503-5_64"},{"key":"55_CR17","doi-asserted-by":"crossref","unstructured":"I. Wegener, The Complexity of Boolean Functions, Wiley-Teubner, 1987.","DOI":"10.1007\/3-540-18170-9_185"},{"key":"55_CR18","doi-asserted-by":"crossref","unstructured":"J. Wang, J. Belanger, On Average P vs. Average NP, Proc. 7. Structure, 1992, 318\u2013326.","DOI":"10.1109\/SCT.1992.215406"}],"container-title":["Lecture Notes in Computer Science","STACS 95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59042-0_111.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:42:15Z","timestamp":1742596935000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59042-0_111"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590422","9783540491750"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-59042-0_111","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}