{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:54:12Z","timestamp":1725551652230},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540638902"},{"type":"electronic","value":"9783540696629"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63890-3_27","type":"book-chapter","created":{"date-parts":[[2010,4,5]],"date-time":"2010-04-05T21:12:11Z","timestamp":1270501931000},"page":"243-252","source":"Crossref","is-referenced-by-count":1,"title":["On the size of probabilistic formulae"],"prefix":"10.1007","author":[{"given":"Hartmut","family":"Klauck","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,7,29]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1016\/0022-0000(92)90047-M","volume":"45","author":"L. Babai","year":"1992","unstructured":"L. Babai, N. Nisan, M. Szegedy. Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-offs. Journ. of Computer and System Sciences, vol.45, pp. 204\u2013232, 1992.","journal-title":"Journ. of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"R.B. Boppana. Amplification of probabilistic Boolean formulas. 26th Symp. Found. Comput. Science, pp. 20\u201329, 1985.","key":"27_CR2","DOI":"10.1109\/SFCS.1985.5"},{"doi-asserted-by":"crossref","unstructured":"R.B. Boppana, M. Sipser. The Complexity of Finite Functions. Handbook of Theoretical Computer Science, vol. A. Elsevier, 1990.","key":"27_CR3","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"key":"27_CR4","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1137\/S009753979223633X","volume":"26","author":"M. Dubiner","year":"1997","unstructured":"M. Dubiner, U. Zwick. Amplification by Read-Once Formulae. SIAM Journal Comput., vol.26, pp. 15\u201338, 1997.","journal-title":"SIAM Journal Comput."},{"doi-asserted-by":"crossref","unstructured":"P. Duri\u0161, J. Hromkovi\u010d, J.D.P. Rolim, G. Schnitger. Las Vegas Versus Determinism for One-way Communication Complexity, Finite Automata, and Polynomial-time Comp. 14th Symp. on Theor. Aspects of Comp. Science, pp. 117\u2013128, 1997.","key":"27_CR5","DOI":"10.1007\/BFb0023453"},{"doi-asserted-by":"crossref","unstructured":"J. Hromkov\u00eec. Communication Complexity and Parallel Computing. Springer, 1997.","key":"27_CR6","DOI":"10.1007\/978-3-662-03442-2"},{"doi-asserted-by":"crossref","unstructured":"I. Kremer, N. Nisan, D. Ron. On Randomized One-Round Communication Complexity. 27th Symp. Theory of Comput., pp. 596\u2013605, 1995.","key":"27_CR7","DOI":"10.1145\/225058.225277"},{"doi-asserted-by":"crossref","unstructured":"E. Kushilevitz, N. Nisan. Communication Complexity. Cambridge University Press, 1996.","key":"27_CR8","DOI":"10.1017\/CBO9780511574948"},{"key":"27_CR9","first-page":"718","volume":"3","author":"M. Karchmer","year":"1990","unstructured":"M. Karchmer, A. Wigderson. Monotone Circuits for Connectivity Require Super-Log. Depth. SIAM Journ. Discrete Math., vol.3, pp. 718\u2013727, 1990.","journal-title":"Depth. SIAM Journ. Discrete Math."},{"key":"27_CR10","first-page":"999","volume":"7","author":"E.I. Ne\u010diporuk","year":"1966","unstructured":"E.I. Ne\u010diporuk. A Boolean function. Sov.Math.Dokl., vol.7, pp. 999\u20131000, 1966.","journal-title":"Sov.Math.Dokl."},{"key":"27_CR11","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"I. Newman","year":"1991","unstructured":"I. Newman. Private vs. Common Random Bits in Communication Complexity. Information Processing Letters, vol.39, pp.67\u201371, 1991.","journal-title":"Information Processing Letters"},{"key":"27_CR12","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/0196-6774(84)90016-6","volume":"5","author":"L.G. Valiant","year":"1984","unstructured":"L.G. Valiant. Short monotone formulae for the majority function. Journal of Algorithms, vol.5, pp. 363\u2013366, 1984.","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63890-3_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T00:37:30Z","timestamp":1559003850000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63890-3_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540638902","9783540696629"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-63890-3_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}