{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T06:29:18Z","timestamp":1772519358821,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540380443","type":"print"},{"value":"9783540380450","type":"electronic"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11830924_38","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T12:33:54Z","timestamp":1156509234000},"page":"410-425","source":"Crossref","is-referenced-by-count":16,"title":["Monotone Circuits for the Majority Function"],"prefix":"10.1007","author":[{"given":"Shlomo","family":"Hoory","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avner","family":"Magen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toniann","family":"Pitassi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"38_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579338","volume":"3","author":"M. Ajtai","year":"1983","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: Sorting in c log n parallel steps. Combinatorica\u00a03(1), 1\u201319 (1983)","journal-title":"Combinatorica"},{"key":"38_CR2","doi-asserted-by":"crossref","unstructured":"Boppana, R.B.: Amplification of probabilistic boolean formulas. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 20\u201329 (1985)","DOI":"10.1109\/SFCS.1985.5"},{"issue":"2","key":"38_CR3","doi-asserted-by":"publisher","first-page":"782","DOI":"10.1109\/18.910588","volume":"47","author":"D. Burshtein","year":"2001","unstructured":"Burshtein, D., Miller, G.: Expander graph arguments for message-passing algorithms. IEEE Trans. Inform. Theory\u00a047(2), 782\u2013790 (2001)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"38_CR4","doi-asserted-by":"crossref","unstructured":"Caplbo, M., Reingold, O., Vadhan, S., Wingderson, A.: Randomness conductors and constant-degree expansion beyond the degree 2 barrier. In: Proceedings 34th Symposium on Theory of Computing, pp. 659\u2013668 (2002)","DOI":"10.1145\/509907.510003"},{"issue":"1","key":"38_CR5","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1137\/S009753979223633X","volume":"26","author":"M. Dubiner","year":"1997","unstructured":"Dubiner, M., Zwick, U.: Amplification by read-once formulas. SIAM J. Comput.\u00a026(1), 15\u201338 (1997)","journal-title":"SIAM J. Comput."},{"key":"38_CR6","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. The Bulletin of the AMS (to appear)"},{"key":"38_CR7","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, Chicago, IL, pp. 539\u2013550 (May 1988)","DOI":"10.1145\/62212.62265"},{"key":"38_CR8","unstructured":"Luby, M., Mitzenmacher, M., Shokrollahi, A.: Analysis of random processes via and-or tree evaluation. In: ACM-SIAM Symp. on Discrete Algorithms (SODA) (1998)"},{"key":"38_CR9","doi-asserted-by":"crossref","unstructured":"Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D.A.: Analysis of low density codes and improved designs using irregular graphs. In: ACM Symposium on Theory of Computing (STOC) (1998)","DOI":"10.1145\/276698.276756"},{"key":"38_CR10","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0016-0032(56)90559-2","volume":"262","author":"E.F. Moore","year":"1956","unstructured":"Moore, E.F., Shannon, C.E.: Reliable circuits using less reliable relays. I, II. J. Franklin Inst.\u00a0262, 191\u2013208, 281\u2013297 (1956)","journal-title":"J. Franklin Inst."},{"issue":"1","key":"38_CR11","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BF01840378","volume":"5","author":"M.S. Paterson","year":"1990","unstructured":"Paterson, M.S.: Improved sorting networks with O(logN) depth. Algorithmica\u00a05(1), 75\u201392 (1990)","journal-title":"Algorithmica"},{"key":"38_CR12","series-title":"London Math. Soc. Lecture Note Ser.","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1017\/CBO9780511526633.014","volume-title":"Boolean function complexity (Durham, 1990)","author":"M.S. Paterson","year":"1992","unstructured":"Paterson, M.S., Pippenger, N., Zwick, U.: Optimal carry save networks. In: Boolean function complexity (Durham, 1990). London Math. Soc. Lecture Note Ser., vol.\u00a0169, pp. 174\u2013201. Cambridge Univ. Press, Cambridge (1992)"},{"key":"38_CR13","unstructured":"Richardson, T., Urbanke, R.: Modern coding theory. Draft of a book"},{"issue":"2","key":"38_CR14","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1109\/18.910577","volume":"47","author":"T. Richardson","year":"2001","unstructured":"Richardson, T., Urbanke, R.: The capacity of low-density parity-check codes under message-passing decoding. IEEE Trans. Inform. Theory\u00a047(2), 599\u2013618 (2001)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"3","key":"38_CR15","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0196-6774(84)90016-6","volume":"5","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G.: Short monotone formulae for the majority function. J. Algorithms\u00a05(3), 363\u2013366 (1984)","journal-title":"J. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11830924_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,8]],"date-time":"2023-05-08T16:21:18Z","timestamp":1683562878000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11830924_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540380443","9783540380450"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/11830924_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}