{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T22:56:54Z","timestamp":1776985014925,"version":"3.51.4"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,6,1]],"date-time":"2020-06-01T00:00:00Z","timestamp":1590969600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,1]],"date-time":"2020-06-01T00:00:00Z","timestamp":1590969600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s00037-020-00194-8","type":"journal-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T12:02:25Z","timestamp":1591444945000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation"],"prefix":"10.1007","volume":"29","author":[{"given":"Or","family":"Meir","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,6,6]]},"reference":[{"issue":"3","key":"194_CR1","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s00037-017-0159-x","volume":"27","author":"Irit Dinur & Or Meir","year":"2018","unstructured":"Irit Dinur & Or Meir: Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. Computational Complexity 27(3), 375\u2013462 (2018)","journal-title":"Computational Complexity"},{"issue":"3","key":"194_CR2","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/s00037-001-8195-x","volume":"10","author":"Jeff Edmonds","year":"2001","unstructured":"Edmonds, Jeff, Impagliazzo, Russell, Rudich, Steven, Sgall, Jiri: Communication complexity towards lower bounds on circuit depth. Computational Complexity 10(3), 210\u2013246 (2001)","journal-title":"Computational Complexity"},{"issue":"1","key":"194_CR3","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1137\/15M1018319","volume":"46","author":"Dmitry Gavinsky","year":"2017","unstructured":"Gavinsky, Dmitry, Meir, Or, Weinstein, Omri, Wigderson, Avi: Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation. SIAM J. Comput. 46(1), 114\u2013131 (2017)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"194_CR4","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1137\/S0097539794261556","volume":"27","author":"Johan H\u00e5stad","year":"1998","unstructured":"H\u00e5stad, Johan: The Shrinkage Exponent of de Morgan Formulas is 2. SIAM J. Comput. 27(1), 48\u201364 (1998)","journal-title":"SIAM J. Comput."},{"key":"194_CR5","volume-title":"Composition of the universal relation","author":"Johan H\u00e5stad & Avi Wigderson","year":"1993","unstructured":"Johan H\u00e5stad & Avi Wigderson: Composition of the universal relation. In Advances in computational complexity theory, AMS-DIMACS (1993)"},{"issue":"1\u201310","key":"194_CR6","first-page":"12","volume":"10","author":"Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin & Alexander V. Smal (2018). Half-Duplex Communication Complexity. In 29th International Symposium on Algorithms and Computation, ISAAC 2018(December), pp. 16\u201319","year":"2018","unstructured":"Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin & Alexander V. Smal (2018). Half-Duplex Communication Complexity. In 29th International Symposium on Algorithms and Computation, ISAAC 2018(December), pp. 16\u201319: Jiaoxi. Yilan, Taiwan 10(1\u201310), 12 (2018)","journal-title":"Yilan, Taiwan"},{"issue":"3\/4","key":"194_CR7","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF01206317","volume":"5","author":"Mauricio Karchmer","year":"1995","unstructured":"Karchmer, Mauricio, Raz, Ran, Wigderson, Avi: Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity. Computational Complexity 5(3\/4), 191\u2013204 (1995)","journal-title":"Computational Complexity"},{"issue":"2","key":"194_CR8","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/0403021","volume":"3","author":"Mauricio Karchmer & Avi Wigderson","year":"1990","unstructured":"Mauricio Karchmer & Avi Wigderson: Monotone Circuits for Connectivity Require Super-Logarithmic Depth. SIAM J. Discrete Math. 3(2), 255\u2013265 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"194_CR9","doi-asserted-by":"publisher","first-page":"50","DOI":"10.4064\/cm-3-1-50-57","volume":"3","author":"Tam\u00e1s K\u0151v\u00e1ri","year":"1954","unstructured":"K\u0151v\u00e1ri, Tam\u00e1s, S\u00f3s, Vera T., Tur\u00e1n, P\u00e1l: On a problem of K. Zarankiewicz. Colloquium Mathematicae 3, 50\u201357 (1954)","journal-title":"Zarankiewicz. Colloquium Mathematicae"},{"key":"194_CR10","unstructured":"Gillat Kol & Ran Raz (2013). Interactive channel capacity. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, 715\u2013724"},{"key":"194_CR11","unstructured":"Sajin Koroth & Or Meir (2018). Improved composition theorems for functions and relations. In RANDOM"},{"key":"194_CR12","doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz & Noam Nisan (1997). Communication complexity. Cambridge University Press. ISBN 978-0-521-56067-2","DOI":"10.1016\/S0065-2458(08)60342-3"},{"key":"194_CR13","doi-asserted-by":"crossref","unstructured":"Norbert Sauer (1972). On the Density of Families of Sets. J. Comb. Theory, Ser. A13(1), 145\u2013147","DOI":"10.1016\/0097-3165(72)90019-2"},{"key":"194_CR14","doi-asserted-by":"publisher","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"Saharon Shelah","year":"1972","unstructured":"Shelah, Saharon: \"A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics 41, 247\u2013261 (1972)","journal-title":"Pacific Journal of Mathematics"},{"key":"194_CR15","unstructured":"G\u00e1bor Tardos & Uri Zwick (1997). The Communication Complexity of the Universal Relation. In Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, Ulm, Germany, June 24-27, 1997, 247\u2013259"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-020-00194-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-020-00194-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-020-00194-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,5]],"date-time":"2021-06-05T23:09:16Z","timestamp":1622934556000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-020-00194-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["194"],"URL":"https:\/\/doi.org\/10.1007\/s00037-020-00194-8","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6]]},"assertion":[{"value":"10 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"4"}}