{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T02:53:50Z","timestamp":1648954430916},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T00:00:00Z","timestamp":1559779200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T00:00:00Z","timestamp":1559779200000},"content-version":"vor","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":[[2019,12]]},"DOI":"10.1007\/s00037-019-00188-1","type":"journal-article","created":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T02:02:31Z","timestamp":1559786551000},"page":"661-708","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Derandomized Composition of Boolean Functions"],"prefix":"10.1007","volume":"28","author":[{"given":"Or","family":"Meir","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,6,6]]},"reference":[{"key":"188_CR1","unstructured":"Arkadev Chattopadhyay, Michal Kouck\u00fd, Bruno Loff & Sagnik Mukhopadhyay (2017). Simulation Theorems via Pseudorandom Properties. CoRR. \n                    http:\/\/arxiv.org\/abs\/1704.06807\n                    \n                  ."},{"key":"188_CR2","unstructured":"Irit Dinur, Prahladh Harsha, Srikanth Srinivasan & Girish Varma (2015). Derandomized Graph Product Results Using the Low Degree Long Code. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, 275\u2013287."},{"key":"188_CR3","unstructured":"Irit Dinur & Or Meir (2016). Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, 3:1\u20133:51."},{"issue":"3","key":"188_CR4","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":"188_CR5","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s004930050045","volume":"19","author":"Peter Frankl & Norihide Tokushige","year":"1999","unstructured":"Peter Frankl & Norihide Tokushige: The Erd\u0151s-Ko-Rado Theorem for Integer Sequences. Combinatorica 19(1), 55\u201363 (1999)","journal-title":"Combinatorica"},{"issue":"1","key":"188_CR6","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."},{"key":"188_CR7","doi-asserted-by":"crossref","unstructured":"Justin Gilmer, Michael E. Saks & Srikanth Srinivasan (2013). Composition Limits and Separating Examples for Some Boolean Function Complexity Measures. In Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013, 185\u2013196.","DOI":"10.1109\/CCC.2013.27"},{"key":"188_CR8","unstructured":"Mika G\u00f6\u00f6s (2015). Lower Bounds for Clique vs. Independent Set. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, 1066\u20131076."},{"key":"188_CR9","unstructured":"Mika G\u00f6\u00f6s, Pritish Kamath, Toniann Pitassi & Thomas Watson (2017). Query-to-Communication Lifting for P\u02c6NP. In 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, 12:1\u201312:16."},{"issue":"5","key":"188_CR10","doi-asserted-by":"publisher","first-page":"1835","DOI":"10.1137\/15M103145X","volume":"45","author":"Mika G\u00f6\u00f6s","year":"2016","unstructured":"G\u00f6\u00f6s, Mika, Lovett, Shachar, Meka, Raghu, Watson, Thomas, Zuckerman, David: Rectangles Are Nonnegative Juntas. SIAM J. Comput. 45(5), 1835\u20131869 (2016)","journal-title":"SIAM J. Comput."},{"key":"188_CR11","unstructured":"Mika G\u00f6\u00f6s, Toniann Pitassi & Thomas Watson (2015). Deterministic Communication vs. Partition Number. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, 1077\u20131088."},{"key":"188_CR12","unstructured":"Michelangelo Grigni & Michael Sipser (1991). Monotone Separation of Logspace from NC. In Structure in Complexity Theory Conference, 294\u2013298."},{"key":"188_CR13","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)"},{"key":"188_CR14","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo (1995). Hard-Core Distributions for Somewhat Hard Problems. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, 23-25 October 1995, 538\u2013545.","DOI":"10.1109\/SFCS.1995.492584"},{"key":"188_CR15","unstructured":"Russell Impagliazzo & Avi Wigderson (1997). P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, 220\u2013229."},{"issue":"1","key":"188_CR16","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1137\/S0895480192238482","volume":"8","author":"Mauricio Karchmer","year":"1995","unstructured":"Karchmer, Mauricio, Kushilevitz, Eyal, Nisan, Noam: Fractional Covers and Communication Complexity. SIAM J. Discrete Math. 8(1), 76\u201392 (1995a)","journal-title":"SIAM J. Discrete Math."},{"issue":"3\/4","key":"188_CR17","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 (1995b)","journal-title":"Computational Complexity"},{"issue":"2","key":"188_CR18","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":"188_CR19","unstructured":"Sajin Koroth & Or Meir (2018). Improved composition theorems for functions and relations. In RANDOM."},{"key":"188_CR20","doi-asserted-by":"crossref","unstructured":"Pravesh K. Kothari, Raghu Meka & Prasad Raghavendra (2017). Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, 590\u2013603.","DOI":"10.1145\/3055399.3055438"},{"key":"188_CR21","first-page":"2016","volume-title":"On Fractional Block Sensitivity","author":"Raghav Kulkarni & Avishay Tal","year":"2016","unstructured":"Raghav Kulkarni & Avishay Tal: On Fractional Block Sensitivity, p. 2016. Chicago J. Theor. Comput, Sci (2016)"},{"key":"188_CR22","unstructured":"James R. Lee, Prasad Raghavendra & David Steurer (2015). Lower Bounds on the Size of Semidefinite Programming Relaxations. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, 567\u2013576."},{"key":"188_CR23","unstructured":"Florence Jessie MacWilliams & Neil James Alexander Sloane (1978). The Theory of Error-Correcting Codes. North-holland Publishing Company, 2nd edition."},{"issue":"3","key":"188_CR24","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1016\/j.jcss.2004.04.002","volume":"69","author":"Elchanan Mossel","year":"2004","unstructured":"Mossel, Elchanan, O'Donnell, Ryan, Servedio, Rocco A.: Learning functions of k relevant variables. J. Comput. Syst. Sci. 69(3), 421\u2013434 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"188_CR25","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/BF01192527","volume":"15","author":"Noam Nisan & Avi Wigderson","year":"1995","unstructured":"Noam Nisan & Avi Wigderson: On Rank vs. Communication Complexity. Combinatorica 15(4), 557\u2013565 (1995)","journal-title":"Combinatorica"},{"issue":"1","key":"188_CR26","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1006\/jcss.1996.0004","volume":"52","author":"Noam Nisan & David Zuckerman","year":"1996","unstructured":"Noam Nisan & David Zuckerman: Randomness is Linear in Space. J. Comput. Syst. Sci. 52(1), 43\u201352 (1996)","journal-title":"J. Comput. Syst. Sci."},{"key":"188_CR27","unstructured":"Ran Raz & Pierre McKenzie (1997). Separation of the Monotone NC Hierarchy. In 38th Annual Symposium on Foundations of Computer Science, FOCS '97, Miami Beach, Florida, USA, October 19-22, 1997, 234\u2013243."},{"issue":"1","key":"188_CR28","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1006\/jcss.2002.1824","volume":"65","author":"Ran Raz","year":"2002","unstructured":"Ran Raz, Omer Reingold & Salil P. Vadhan (2002). Extracting all the Randomness and Reducing the Error in Trevisan's Extractors. J. Comput. Syst. Sci.\n                           65(1), 97\u2013128. URL \n                    https:\/\/doi.org\/10.1006\/jcss.2002.1824\n                    \n                  .","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"188_CR29","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1145\/146637.146684","volume":"39","author":"Ran Raz & Avi Wigderson","year":"1992","unstructured":"Ran Raz & Avi Wigderson: Monotone Circuits for Matching Require Linear Depth. J. ACM 39(3), 736\u2013744 (1992)","journal-title":"J. ACM"},{"issue":"1","key":"188_CR30","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02122698","volume":"10","author":"Alexander A Razborov","year":"1990","unstructured":"Razborov, Alexander A.: Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica 10(1), 81\u201393 (1990)","journal-title":"Combinatorica"},{"key":"188_CR31","unstructured":"Alexander A. Razborov (2016). A New Kind of Tradeoffs in Propositional Proof Complexity. J. ACM\n                           63(2), 16:1\u201316:14."},{"key":"188_CR32","doi-asserted-by":"crossref","unstructured":"Ronen Shaltiel (2010). Derandomized Parallel Repetition Theorems for Free Games. In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, June 9-12, 2010, 28\u201337.","DOI":"10.1109\/CCC.2010.12"},{"issue":"6","key":"188_CR33","doi-asserted-by":"publisher","first-page":"1969","DOI":"10.1137\/080733644","volume":"40","author":"Alexander A Sherstov","year":"2011","unstructured":"Sherstov, Alexander A.: The Pattern Matrix Method. SIAM J. Comput. 40(6), 1969\u20132000 (2011)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"188_CR34","first-page":"444","volume":"9","author":"Yaoyun Shi & Yufan Zhu","year":"2009","unstructured":"Yaoyun Shi & Yufan Zhu: Quantum communication complexity of block-composed functions. Quantum Information & Computation 9(5), 444\u2013460 (2009)","journal-title":"Quantum Information & Computation"},{"key":"188_CR35","doi-asserted-by":"crossref","unstructured":"Avishay Tal (2013). Properties and applications of boolean function composition. In Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013, 441\u2013454.","DOI":"10.1145\/2422436.2422485"},{"key":"188_CR36","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."},{"key":"188_CR37","first-page":"10","volume":"24","author":"Wu Xiaodi","year":"2017","unstructured":"Xiaodi, Wu, Yao, Penghui, Yuen, Henry S.: Raz-McKenzie simulation with the inner product gadget. Electronic Colloquium on Computational Complexity (ECCC) 24, 10 (2017)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"188_CR38","unstructured":"Andrew Chi-Chih Yao (1979). Some Complexity Questions Related to Distributive Computing (Preliminary Report). In STOC, 209\u2013213."},{"issue":"4","key":"188_CR39","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.0.CO;2-Z","volume":"11","author":"David Zuckerman","year":"1997","unstructured":"Zuckerman, David: Randomness-optimal oblivious sampling. Random Struct. Algorithms 11(4), 345\u2013367 (1997)","journal-title":"Random Struct. Algorithms"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-019-00188-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-019-00188-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-019-00188-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,4]],"date-time":"2020-06-04T23:28:47Z","timestamp":1591313327000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-019-00188-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,6]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["188"],"URL":"https:\/\/doi.org\/10.1007\/s00037-019-00188-1","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,6]]},"assertion":[{"value":"8 July 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2019","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}