{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T22:56:12Z","timestamp":1776984972020,"version":"3.51.4"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,7,27]],"date-time":"2017-07-27T00:00:00Z","timestamp":1501113600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2018,9]]},"DOI":"10.1007\/s00037-017-0159-x","type":"journal-article","created":{"date-parts":[[2017,7,27]],"date-time":"2017-07-27T08:29:46Z","timestamp":1501144186000},"page":"375-462","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity"],"prefix":"10.1007","volume":"27","author":[{"given":"Irit","family":"Dinur","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Or","family":"Meir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,27]]},"reference":[{"key":"159_CR1","unstructured":"Alexander E. Andreev (1987). On a Method for Obtaining more than Quadratic Effective Lower Bounds for the Complexity of \u03c0-Schemes. Moscow University Mathematics Bulletin 42(1), 24\u201329."},{"key":"159_CR2","doi-asserted-by":"crossref","unstructured":"Boaz Barak, Mark Braverman, Xi Chen & Anup Rao (2010). How to compress interactive communication. In STOC, 67\u201376.","DOI":"10.1145\/1806689.1806701"},{"key":"159_CR3","doi-asserted-by":"crossref","unstructured":"Amos Beimel, Sebastian Ben Daniel, Eyal Kushilevitz & Enav Weinreb (2014). Choosing, Agreeing, and Eliminating in Communication Complexity. Computational Complexity 23(1), 1\u201342.","DOI":"10.1007\/s00037-013-0075-7"},{"key":"159_CR4","doi-asserted-by":"crossref","unstructured":"Maria Luisa Bonet & Samuel R. Buss (1994). Size-Depth Tradeoffs for Boolean Formulae. Inf. Process. Lett. 49(3), 151\u2013155.","DOI":"10.1016\/0020-0190(94)90093-0"},{"key":"159_CR5","doi-asserted-by":"crossref","unstructured":"Mark Braverman (2012). Interactive information complexity. In STOC, 505\u2013524.","DOI":"10.1145\/2213977.2214025"},{"key":"159_CR6","doi-asserted-by":"crossref","unstructured":"Mark Braverman & Anup Rao (2011). Information Equals Amortized Communication. In FOCS, 748\u2013757.","DOI":"10.1109\/FOCS.2011.86"},{"key":"159_CR7","doi-asserted-by":"crossref","unstructured":"Richard P. Brent (1974). The Parallel Evaluation of General Arithmetic Expressions. J. ACM 21(2): 201\u2013206","DOI":"10.1145\/321812.321815"},{"key":"159_CR8","doi-asserted-by":"crossref","unstructured":"Ruiwen Chen, Valentine Kabanets, Antonina Kolokolova, Ronen Shaltiel & David Zuckerman (2015). Mining Circuit Lower Bound Proofs for Meta-Algorithms. Computational Complexity 24(2), 333\u2013392.","DOI":"10.1007\/s00037-015-0100-0"},{"key":"159_CR9","doi-asserted-by":"crossref","unstructured":"Thomas M. Cover & Joy A. Thomas (1991). Elements of information theory. Wiley-Interscience. ISBN 0-471-06259-6.","DOI":"10.1002\/0471200611"},{"key":"159_CR10","doi-asserted-by":"crossref","unstructured":"Jeff Edmonds, Russell Impagliazzo, Steven Rudich & Jiri Sgall (2001). Communication complexity towards lower bounds on circuit depth. Computational Complexity 10(3), 210\u2013246.","DOI":"10.1007\/s00037-001-8195-x"},{"key":"159_CR11","doi-asserted-by":"crossref","unstructured":"Tom\u00e1s Feder, Eyal Kushilevitz, Moni Naor & Noam Nisan (1995). Amortized Communication Complexity. SIAM J. Comput.24(4), 736\u2013750.","DOI":"10.1137\/S0097539792235864"},{"key":"159_CR12","doi-asserted-by":"crossref","unstructured":"Dmitry Gavinsky, Or Meir, Omri Weinstein & Avi Wigderson (2014). Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31\u2013June 03, 2014, 213\u2013222.","DOI":"10.1145\/2591796.2591856"},{"key":"159_CR13","unstructured":"Michelangelo Grigni & Michael Sipser (1991). Monotone Separation of Logspace from NC. In Structure in Complexity Theory Conference, 294\u2013298."},{"issue":"1","key":"159_CR14","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1137\/S0097539794261556","volume":"27","author":"H\u00e5stad Johan","year":"1998","unstructured":"Johan H\u00e5stad (1998) The Shrinkage Exponent of de Morgan Formulas is 2. SIAM J. Comput. 27(1): 48\u201364","journal-title":"SIAM J. Comput."},{"key":"159_CR15","doi-asserted-by":"crossref","unstructured":"Johan H\u00e5stad & Avi Wigderson (1993). Composition of the universal relation. In Advances in computational complexity theory, AMS-DIMACS.","DOI":"10.1090\/dimacs\/013\/07"},{"key":"159_CR16","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo & Noam Nisan (1993). The Effect of Random Restrictions on Formula Size. Random Struct. Algorithms 4(2), 121\u2013134.","DOI":"10.1002\/rsa.3240040202"},{"key":"159_CR17","unstructured":"Stasys Jukna (2012). Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and combinatorics. Springer. ISBN 978-3-642-24507-7, I-XV, 1-617 ."},{"key":"159_CR18","unstructured":"Yael Tauman Kalai & Ran Raz (2008). Interactive PCP. In ICALP (2), 536\u2013547."},{"key":"159_CR19","doi-asserted-by":"crossref","unstructured":"Mauricio Karchmer, Eyal Kushilevitz & Noam Nisan (1995a). Fractional Covers and Communication Complexity. SIAM J. Discrete Math. 8(1), 76\u201392.","DOI":"10.1137\/S0895480192238482"},{"key":"159_CR20","doi-asserted-by":"crossref","unstructured":"Mauricio Karchmer, Ran Raz & Avi Wigderson (1995b). Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity. Computational Complexity 5(3\/4), 191\u2013204.","DOI":"10.1007\/BF01206317"},{"key":"159_CR21","doi-asserted-by":"crossref","unstructured":"Mauricio Karchmer & Avi Wigderson (1990). Monotone Circuits for Connectivity Require Super-Logarithmic Depth. SIAM J. Discrete Math.3(2), 255\u2013265.","DOI":"10.1137\/0403021"},{"key":"159_CR22","first-page":"474","volume":"10","author":"V.M. Khrapchenko","year":"1972","unstructured":"Khrapchenko V.M. (1972) A method of obtaining lower bounds for the complexity of \u03c0-schemes. Mathematical Notes Academy of Sciences USSR 10: 474\u2013479","journal-title":"Mathematical Notes Academy of Sciences USSR"},{"key":"159_CR23","doi-asserted-by":"crossref","unstructured":"Ilan Komargodski & Ran Raz (2013). Average-case lower bounds for formula size. In Symposium on Theory of Computing Conference, STOC\u201913, Palo Alto, CA, USA, June 1\u20134, 2013, 171\u2013180.","DOI":"10.1145\/2488608.2488630"},{"key":"159_CR24","doi-asserted-by":"crossref","unstructured":"Ilan Komargodski, Ran Raz & Avishay Tal (2013). Improved Average-Case Lower Bounds for DeMorgan Formula Size. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26\u201329 October, 2013, Berkeley, CA, USA, 588\u2013597.","DOI":"10.1109\/FOCS.2013.69"},{"key":"159_CR25","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":"159_CR26","doi-asserted-by":"crossref","unstructured":"Dana Moshkovitz (2014). Parallel Repetition from Fortification. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18\u201321, 2014, 414\u2013423.","DOI":"10.1109\/FOCS.2014.51"},{"issue":"2","key":"159_CR27","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1002\/rsa.3240040203","volume":"4","author":"Paterson Mike","year":"1993","unstructured":"Mike Paterson, Uri Zwick (1993) Shrinkage of de Morgan Formulae under Restriction. Random Struct. Algorithms 4(2): 135\u2013150","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"159_CR28","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1145\/146637.146684","volume":"39","author":"Raz Ran","year":"1992","unstructured":"Ran Raz, Avi Wigderson (1992) Monotone Circuits for Matching Require Linear Depth. J. ACM 39(3): 736\u2013744","journal-title":"J. ACM"},{"key":"159_CR29","doi-asserted-by":"crossref","unstructured":"Alexander A. Razborov (1990). Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica 10(1), 81\u201393.","DOI":"10.1007\/BF02122698"},{"key":"159_CR30","doi-asserted-by":"crossref","unstructured":"Rahul Santhanam (2010). Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23\u201326, 2010, Las Vegas, Nevada, USA, 183\u2013192.","DOI":"10.1109\/FOCS.2010.25"},{"key":"159_CR31","unstructured":"Philip M. Spira (1971). On time-hardware complexity tradeoffs for Boolean functions. In Proceedings of the Fourth Hawaii International Symposium on System Sciences, 525\u2013527."},{"key":"159_CR32","unstructured":"Bella Abramovna Subbotovskaya (1961). Realizations of linear functions by formulas using +,.,-. Soviet Mathematics Doklady 2, 110\u2013112."},{"key":"159_CR33","unstructured":"Madhu Sudan (2001). Algorithmic introduction to coding theory (Lecture notes). Available from http:\/\/theory.csail.mit.edu\/~madhu\/FT01\/ ."},{"key":"159_CR34","doi-asserted-by":"crossref","unstructured":"Avishay Tal (2014). Shrinkage of De Morgan Formulae by Spectral Techniques. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18\u201321, 2014, 551\u2013560.","DOI":"10.1109\/FOCS.2014.65"},{"key":"159_CR35","unstructured":"Andrew Chi-Chih Yao (1979). Some Complexity Questions Related to Distributive Computing (Preliminary Report). In STOC, 209\u2013213."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-017-0159-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0159-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0159-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,13]],"date-time":"2020-10-13T16:57:34Z","timestamp":1602608254000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-017-0159-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,27]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["159"],"URL":"https:\/\/doi.org\/10.1007\/s00037-017-0159-x","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,7,27]]}}}