{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T13:25:52Z","timestamp":1726406752920},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540603139"},{"type":"electronic","value":"9783540449133"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60313-1_137","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T18:17:58Z","timestamp":1330280278000},"page":"102-112","source":"Crossref","is-referenced-by-count":2,"title":["Average circuit depth and average communication complexity"],"prefix":"10.1007","author":[{"given":"Bruno","family":"Codenotti","sequence":"first","affiliation":[]},{"given":"Peter","family":"Gemmell","sequence":"additional","affiliation":[]},{"given":"Janos","family":"Simon","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"T. Feder, E. Kushilevitz, M. Naor, Amortized Communication Complexity, Proc. 32nd Symposium on the Foundations of Computer Science, October 1991, pp. 239\u2013248.","DOI":"10.1109\/SFCS.1991.185374"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"A. Jakoby, R. Reischuk, C. Schindelhauer, Circuit Complexity: from the Worst Case to the Average Case, Proc. 26th ACM Symposium on the Theory of Computing, May 1994, pp.58\u201367.","DOI":"10.1145\/195058.195106"},{"issue":"no2","key":"8_CR3","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1137\/0403021","volume":"3","author":"M. Karchmer","year":"1990","unstructured":"M. Karchmer and A. Wigderson, Monotone Circuits for Connectivity Require Superlogarithmic Depth, Siam Journal of Discrete Math, vol. 3, no 2, May 1990, pp.255\u2013265.","journal-title":"Siam Journal of Discrete Math"},{"key":"8_CR4","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L. Levin","year":"1986","unstructured":"L. Levin, Average Case Complexity Problems, SIAM J. Computing 15, 1986, pp. 285\u2013286.","journal-title":"SIAM J. Computing"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"A. Orlitsky, Interactive Communication: Balanced Distributions, Correlated Files, and Average-Case Complexity, Proc. 32nd Symposium on the Foundations of Computer Science, October 1991, pp. 228\u2013238.","DOI":"10.1109\/SFCS.1991.185373"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"R. Raz and A. Wigderson, Probabilistic Communication Complexity of Boolean Relations, Proc. 30th Symposium on the Foundations of Computer Science, October 1989, pp. 562\u2013567.","DOI":"10.1109\/SFCS.1989.63535"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"R. Raz and A. Wigderson, Monotone Circuits for Matching Require Linear Depth, Journal of the ACM v.39 1992.","DOI":"10.1145\/146637.146684"},{"issue":"n.6","key":"8_CR8","first-page":"887","volume":"37","author":"A. A. Razborov","year":"1985","unstructured":"A. A. Razborov, A lower bound on the monotone network complexity of the logical permanent Mat. Zametki v.37 n.6 1985 pp. 887\u2013900.","journal-title":"Mat. Zametki"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"R. Reischuk, C. Schindelhauer, Precise Average Case Complexity, Proc. 10th Symposium on Theoretical Aspects of Computer Science, Feb. 1993, pp.650\u2013661.","DOI":"10.1007\/3-540-56503-5_64"},{"issue":"n.3","key":"8_CR10","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(84)90013-9","volume":"18","author":"H. S. Wilf","year":"1984","unstructured":"H. S. Wilf, Backtrack: An O(1) expected time algorithm for the graph coloring problem, Information Processing Letters v.18 n.3 1984 pp. 119\u2013121.","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60313-1_137.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:58:02Z","timestamp":1605646682000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60313-1_137"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540603139","9783540449133"],"references-count":10,"URL":"http:\/\/dx.doi.org\/10.1007\/3-540-60313-1_137","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}
