{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:40:22Z","timestamp":1742600422249,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_25","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:03:57Z","timestamp":1330290237000},"page":"293-306","source":"Crossref","is-referenced-by-count":1,"title":["On the complexity of worst case and expected time in a circuit"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Jakoby","sequence":"first","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,7]]},"reference":[{"key":"25_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"},{"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.","key":"25_CR2","DOI":"10.1142\/S0129626495000254"},{"doi-asserted-by":"crossref","unstructured":"S. A. Cook, The Complexity of Theorem-Proving Procedures, Proc. of the 3rd IEEE Symp. on the Foundations of Computer Science, 151\u2013158, 1971.","key":"25_CR3","DOI":"10.1145\/800157.805047"},{"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 SIGARCH, 1989, 91\u2013104.","key":"25_CR4","DOI":"10.1109\/EEIS.1989.720129"},{"unstructured":"R. Greenlaw, H. J. Hoover, W. L. Ruzzo, A Compendium of Problems Complete for P, Technical Report 91-05-01, University of Washington, 1991.","key":"25_CR5"},{"doi-asserted-by":"crossref","unstructured":"A. Jakoby, R. Reischuk, C. Schindelhauer, Circuit Complexity: from the Worst Case to the Average Case, Proc. 26th SToC, 1994, 58\u201367; see also Technical Report, TH Darmstadt, 1993.","key":"25_CR6","DOI":"10.1145\/195058.195106"},{"doi-asserted-by":"crossref","unstructured":"A. Jakoby, R. Reischuk, C. Schindelhauer, Malign Distributions for Average Case Circuit Complexity, Proc. 12th STACS, 1995, 628\u2013639.","key":"25_CR7","DOI":"10.1007\/3-540-59042-0_111"},{"doi-asserted-by":"crossref","unstructured":"A. Jakoby, R. Reischuk, C. Schindelhauer, S. Weis The Average Case Complexity of the Parallel Prefix Problem, Proc. 21st ICALP, 1994, 593\u2013604; Technical Report, TH Darmstadt, 1993.","key":"25_CR8","DOI":"10.1007\/3-540-58201-0_101"},{"key":"25_CR9","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."},{"doi-asserted-by":"crossref","unstructured":"M. W. Krentel The complexity of optimization problems, Proc. 18th SToC, 1986, 79\u201386; see also J. CSS 36, 1988, 490\u2013509.","key":"25_CR10","DOI":"10.1016\/0022-0000(88)90039-6"},{"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.","key":"25_CR11","DOI":"10.1145\/157485.164625"},{"key":"25_CR12","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":"25_CR13","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1137\/0222012","volume":"22","author":"P. Miltersen","year":"1993","unstructured":"P. Miltersen, The Complexity of Malign Ensembles, SIAM. J. Comput. 22, 1993, 147\u2013156.","journal-title":"SIAM. J. Comput."},{"doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou, M. Yannakakis, The Complexity of Facets (and some facets of complexity), Proc. 14th SToC, 1982, 255\u2013260; also, J.CSS 28, 1984, 244\u2013259.","key":"25_CR14","DOI":"10.1016\/0022-0000(84)90068-0"},{"unstructured":"C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.","key":"25_CR15"},{"key":"25_CR16","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0898-1221(93)90089-E","volume":"26","author":"J. Reif","year":"1993","unstructured":"J. Reif, Probabilistic Parallel Prefix Computation, Comp. Math. Applic. 26, 1993, 101\u2013110.","journal-title":"Comp. Math. Applic."},{"doi-asserted-by":"crossref","unstructured":"S. Toda, The Complexity of Finding Medians, 31th FoCS, 1990, 778\u2013787.","key":"25_CR17","DOI":"10.1109\/FSCS.1990.89600"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:10:34Z","timestamp":1742598634000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}