{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:51:35Z","timestamp":1744217495748,"version":"3.37.3"},"reference-count":60,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,1,14]],"date-time":"2014-01-14T00:00:00Z","timestamp":1389657600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2015,9]]},"DOI":"10.1007\/s00037-013-0078-4","type":"journal-article","created":{"date-parts":[[2014,1,13]],"date-time":"2014-01-13T09:08:31Z","timestamp":1389604111000},"page":"645-694","source":"Crossref","is-referenced-by-count":4,"title":["The NOF Multiparty Communication Complexity of Composed Functions"],"prefix":"10.1007","volume":"24","author":[{"given":"Anil","family":"Ada","sequence":"first","affiliation":[]},{"given":"Arkadev","family":"Chattopadhyay","sequence":"additional","affiliation":[]},{"given":"Omar","family":"Fawzi","sequence":"additional","affiliation":[]},{"given":"Phuong","family":"Nguyen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,1,14]]},"reference":[{"key":"78_CR1","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"Alon Noga","year":"1999","unstructured":"Noga Alon, Yossi Matias, Mario Szegedy (1999) The Space Complexity of Approximating the Frequency Moments. Journal of Computer and System Sciences 58: 137\u2013147","journal-title":"Journal of Computer and System Sciences"},{"key":"78_CR2","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai, Anna G\u00e1l, Peter G. Kimmel & Satyanarayana V. Lokam (2003). Communication Complexity of Simultaneous Messages. SIAM Journal on Computing 33, 137\u2013166.","DOI":"10.1137\/S0097539700375944"},{"key":"78_CR3","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai, Peter G. Kimmel & Satyanarayana V. Lokam (1995). Simultaneous messages vs. communication. In In 12th Annual Symposium on Theoretical Aspects of Computer Science (STACS), 361\u2013372. Springer.","DOI":"10.1007\/3-540-59042-0_88"},{"issue":"2","key":"78_CR4","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1016\/0022-0000(92)90047-M","volume":"45","author":"Babai L\u00e1szl\u00f3","year":"1992","unstructured":"L\u00e1szl\u00f3 Babai, Noam Nisan, Mario Szegedy (1992) Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. Journal of Computer and System Sciences 45(2): 204\u2013232","journal-title":"Journal of Computer and System Sciences"},{"key":"78_CR5","unstructured":"Michael Bateman & Nets H. Katz (2011). New bounds on cap sets. URL http:\/\/arxiv.org\/abs\/1101.5851v2 ."},{"key":"78_CR6","doi-asserted-by":"crossref","unstructured":"Paul Beame, Matei David, Toniann Pitassi & Philipp Woelfel (2010). Separating Deterministic from Randomized Multiparty Communication Complexity. Theory of Computing 6(1), 201\u2013225. URL http:\/\/www.theoryofcomputing.org\/articles\/v006a009 .","DOI":"10.4086\/toc.2010.v006a009"},{"key":"78_CR7","doi-asserted-by":"crossref","unstructured":"Paul Beame& Dang-Trinh Huynh-Ngoc (2009). Multiparty Communication Complexity and Threshold Circuit Size of AC 0. In Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201909, 53\u201362. IEEE Computer Society, Washington, DC, USA. URL http:\/\/dx.doi.org\/10.1109\/FOCS.2009.12 .","DOI":"10.1109\/FOCS.2009.12"},{"key":"78_CR8","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1073\/pnas.32.12.331","volume":"32","author":"Behrend Felix A.","year":"1946","unstructured":"Felix A. Behrend (1946) On Sets of Integers Which Contain No Three Terms in Arithmetical Progression. Proceedings of the National Academy of Sciences 32: 331\u2013332","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"78_CR9","doi-asserted-by":"crossref","unstructured":"Richard Beigel, William Gasarch & James Glenn (2006). The Multiparty Communication Complexity of Exact T: Improved Bounds and New Problems. In Mathematical Foundations of Computer Science 2006, Rastislav Kr\u00e1lovic & Pawel Urzyczyn, editors, volume 4162 of Lecture Notes in Computer Science, 146\u2013156. Springer Berlin Heidelberg. URL http:\/\/dx.doi.org\/10.1007\/11821069_13 .","DOI":"10.1007\/11821069_13"},{"key":"78_CR10","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1007\/BF01263423","volume":"4","author":"Beigel Richard","year":"1994","unstructured":"Richard Beigel, Jun Tarui (1994) On ACC. Computational Complexity 4: 350\u2013366","journal-title":"Computational Complexity"},{"key":"78_CR11","doi-asserted-by":"crossref","unstructured":"Eric Blais, Joshua Brody & Kevin Matulef (2011). Property Testing Lower Bounds via Communication Complexity. In In Proceedings of the 2011 IEEE 26th Annual Conference on Computational Complexity (CCC).","DOI":"10.1109\/CCC.2011.31"},{"key":"78_CR12","doi-asserted-by":"crossref","unstructured":"Jean Bourgain (1999). On triples in arithmetic progression. Geometric and Functional Analysis.","DOI":"10.1007\/s000390050105"},{"key":"78_CR13","doi-asserted-by":"crossref","unstructured":"Ashok K. Chandra, Merrick L. Furst & Richard J. Lipton (1983). Multi-party protocols. In Proceedings of the fifteenth annual ACM symposium on Theory of computing, STOC \u201983, 94\u201399. ACM, New York, NY, USA. URL http:\/\/doi.acm.org\/10.1145\/800061.808737 .","DOI":"10.1145\/800061.808737"},{"key":"78_CR14","unstructured":"Arkadev Chattopadhyay (2008). Circuits, Communication and Polynomials. Ph.D. thesis, McGill University."},{"key":"78_CR15","unstructured":"Arkadev Chattopadhyay & Anil Ada (2008). Multiparty communication complexity of disjointness. Technical report, In Electronic Colloquium on Computational Complexity (ECCC) TR08\u2013002."},{"key":"78_CR16","doi-asserted-by":"crossref","unstructured":"Arkadev Chattopadhyay, Andreas Krebs, Michal Koucky, Mario Szegedy, Pascal Tesson & Denis Th\u00e9rien (2007). Languages with bounded multiparty communication complexity. In Proceedings of the 24th annual conference on Theoretical aspects of computer science, STACS\u201907, 500\u2013511. Springer-Verlag, Berlin, Heidelberg. URL http:\/\/portal.acm.org\/citation.cfm?id=1763424.1763484 .","DOI":"10.1007\/978-3-540-70918-3_43"},{"key":"78_CR17","doi-asserted-by":"crossref","unstructured":"Benny Chor & Oded Goldreich (1988). Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput. 17(2), 230\u2013261. ISSN 0097-5397. URL http:\/\/dx.doi.org\/10.1137\/0217015 .","DOI":"10.1137\/0217015"},{"issue":"1","key":"78_CR18","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1137\/0406009","volume":"6","author":"Chung Fan R.K.","year":"1993","unstructured":"Fan R.K. Chung, Prasad Tetali (1993) Communication complexity and quasi randomness. SIAM Journal on Discrete Mathematics 6(1): 110\u2013123","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"78_CR19","doi-asserted-by":"crossref","unstructured":"Vincent Conitzer & Tuomas Sandholm (2004). Communication complexity as a lower bound for learning in games. In International Conference on Machine Learning.","DOI":"10.1145\/1015330.1015351"},{"issue":"(1","key":"78_CR20","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/s11856-011-0061-1","volume":"184","author":"Elkin Michael","year":"2011","unstructured":"Michael Elkin (2011) An improved construction of progression-free sets. Israel Journal of Mathematics 184((1): 93\u2013128","journal-title":"Israel Journal of Mathematics"},{"key":"78_CR21","unstructured":"J\u00fcrgen Forster, Matthias Krause, Satyanarayana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt & Hans ulrich Simon (2001). Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity. In Foundations of Software Technology and Theoretical Computer Science, 171\u2013182."},{"key":"78_CR22","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/BF02790016","volume":"34","author":"Furstenberg Harry","year":"1978","unstructured":"Harry Furstenberg, Yitzhak Katznelson (1978) An ergodic Szemer\u00e9di theorem for commuting transformations. Journal d\u2019Analyse Mathematique 34: 275\u2013291","journal-title":"Journal d\u2019Analyse Mathematique"},{"key":"78_CR23","doi-asserted-by":"crossref","unstructured":"W. Timothy Gowers (2001). A new proof of Szemer\u00e9di\u2019s theorem. Geometric and Functional Analysis 11, 465\u2013588.","DOI":"10.1007\/s00039-001-0332-9"},{"key":"78_CR24","doi-asserted-by":"crossref","unstructured":"W. Timothy Gowers (2007). Hypergraph regularity and the multidimensional Szemer\u00e9di theorem. Annals of Mathematics 166, 897\u2013946.","DOI":"10.4007\/annals.2007.166.897"},{"key":"78_CR25","doi-asserted-by":"crossref","unstructured":"W. Timothy Gowers (2010). Decompositions, approximate structure, transference, and the Hahn-Banach theorem. Bulletin of the London Mathematical Society 42, 573\u2013606.","DOI":"10.1112\/blms\/bdq018"},{"key":"78_CR26","unstructured":"Ben Green (2005). Surveys in Combinatorics 2005, chapter Finite field models in additive combinatorics, 1\u201327. London Math. Soc. Lecture Notes 327. Cambridge Univ Press."},{"key":"78_CR27","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1006\/inco.1994.1051","volume":"112","author":"Grolmusz Vince","year":"1994","unstructured":"Vince Grolmusz (1994) The BNSLower Bound for Multi-party Protocols Is Nearly Optimal. Information and Computation 112: 51\u201354","journal-title":"Information and Computation"},{"key":"78_CR28","doi-asserted-by":"crossref","unstructured":"Vince Grolmusz (1995). Separating the Communication Complexities of MOD m and MOD p Circuits. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS), 278\u2013287.","DOI":"10.1006\/jcss.1995.1069"},{"key":"78_CR29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00001592","volume":"7","author":"Grolmusz Vince","year":"1998","unstructured":"Vince Grolmusz (1998) Circuits and Multi-Party Protocols. Computational Complexity 7: 1\u201318","journal-title":"Computational Complexity"},{"key":"78_CR30","first-page":"610","volume":"1","author":"H\u00e5stad Johan","year":"1991","unstructured":"Johan H\u00e5stad, Mikael Goldmann (1991) On The Power Of Small-Depth Threshold Circuits. Computational Complexity 1: 610\u2013618","journal-title":"Computational Complexity"},{"key":"78_CR31","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1137\/S0097539702405620","volume":"37","author":"Klauck Hartmut","year":"2007","unstructured":"Hartmut Klauck (2007) Lower Bounds for Quantum Communication Complexity. Siam Journal on Computing 37: 20\u201346","journal-title":"Siam Journal on Computing"},{"key":"78_CR32","doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz & Noam Nisan (1997). Communication complexity. Cambridge University Press.","DOI":"10.1016\/S0065-2458(08)60342-3"},{"key":"78_CR33","unstructured":"Michael T. Lacey & William McClain (2007). On an Argument of Shkredov on Two-Dimensional Corners. Online Journal of Analytic Combinatorics."},{"key":"78_CR34","doi-asserted-by":"crossref","unstructured":"Troy Lee, Gideon Schechtman & Adi Shraibman (2009). Lower bounds on quantum multiparty communication complexity. In In Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC), 254\u2013262.","DOI":"10.1109\/CCC.2009.24"},{"key":"78_CR35","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/s00037-009-0276-2","volume":"18","author":"Lee Troy","year":"2009","unstructured":"Troy Lee, Adi Shraibman (2009) Disjointness is Hard in the Multiparty Number-on-the-Forehead Model. Computational Complexity 18: 309\u2013336","journal-title":"Computational Complexity"},{"key":"78_CR36","doi-asserted-by":"crossref","unstructured":"Peter Bro Miltersen, Noam Nisan, Shmuel Safra & Avi Wigderson (1998). On Data Structures and Asymmetric Communication Complexity. Journal of Computer and System Sciences 57(1), 37\u201349. URL http:\/\/www.sciencedirect.com\/science\/article\/pii\/S002200009891577X .","DOI":"10.1006\/jcss.1998.1577"},{"key":"78_CR37","unstructured":"Ashley Montanaro & Tobias Osborne (2009). On the communication complexity of XOR functions. Arxiv preprint arXiv:0909.3392."},{"key":"78_CR38","unstructured":"N. Nisan (1993). The communication complexity of threshold gates. Combinatorica."},{"key":"78_CR39","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1016\/j.jet.2004.10.007","volume":"129","author":"Nisan Noam","year":"2006","unstructured":"Noam Nisan, Ilya Segal (2006) The communication requirements of efficient allocations and supporting prices. Journal of Economic Theory 129: 192\u2013224","journal-title":"Journal of Economic Theory"},{"key":"78_CR40","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1137\/0222016","volume":"22","author":"Nisan Noam","year":"1993","unstructured":"Noam Nisan, Avi Wigderson (1993) Rounds in Communication Complexity Revisited. SIAM Journal on Computing 22: 211\u2013219","journal-title":"SIAM Journal on Computing"},{"key":"78_CR41","doi-asserted-by":"crossref","unstructured":"Kevin O\u2019Bryant (2011). Sets of integers that do not contain long arithmetic progressions. The Electronic Journal of Combinatorics 18(1), 59.","DOI":"10.37236\/546"},{"key":"78_CR42","doi-asserted-by":"crossref","unstructured":"Beame Paul, Toniann Pitassi & Nathan Segerlind (2007). Lower Bounds for Lov\u00e1sz-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. SIAM Journal on Computing 37, 845\u2013869. URL http:\/\/portal.acm.org\/citation.cfm?id=1328865.1328873 .","DOI":"10.1137\/060654645"},{"key":"78_CR43","doi-asserted-by":"crossref","unstructured":"Pavel Pudl\u00e1k (2003). An Application of Hindman\u2019s Theorem to a Problem on Communication Complexity. Combinatorics, Probability & Computing 12, 661\u2013670. URL http:\/\/portal.acm.org\/citation.cfm?id=970118.970134 .","DOI":"10.1017\/S0963548303005790"},{"key":"78_CR44","unstructured":"Pavel Pudl\u00e1k (2006). Personal communication."},{"key":"78_CR45","doi-asserted-by":"crossref","unstructured":"Ran Raz (1995). Fourier Analysis for Probabilistic Communication Complexity. Computational Complexity 5, 205\u2013221.","DOI":"10.1007\/BF01206318"},{"issue":"2","key":"78_CR46","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/PL00001602","volume":"9","author":"Raz Ran","year":"2000","unstructured":"Ran Raz (2000) The BNS-Chung criterion for multi-party communication complexity. Computational Complexity 9(2): 113\u2013122","journal-title":"Computational Complexity"},{"issue":"1","key":"78_CR47","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1070\/IM2003v067n01ABEH000422","volume":"67","author":"Razborov Alexander","year":"2003","unstructured":"Alexander Razborov (2003) Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics 67(1): 145\u2013159","journal-title":"Izvestiya: Mathematics"},{"key":"78_CR48","doi-asserted-by":"crossref","unstructured":"Klaus F. Roth (1953). On Certain Sets of Integers. Journal of The London Mathematical Society-second Series s1-28, 104\u2013109.","DOI":"10.1112\/jlms\/s1-28.1.104"},{"key":"78_CR49","doi-asserted-by":"crossref","first-page":"619","DOI":"10.4007\/annals.2011.174.1.20","volume":"174","author":"Sanders Tom","year":"2011","unstructured":"Tom Sanders (2011) On Roths theorem on progressions. Annals of Mathematics 174: 619\u2013636","journal-title":"Annals of Mathematics"},{"key":"78_CR50","unstructured":"Alexander A. Sherstov (2007). The pattern matrix method for lower bounds on quantum communication. In In Proceedings of the 40th Symposium on Theory of Computing (STOC), 85\u201394."},{"key":"78_CR51","doi-asserted-by":"crossref","unstructured":"Alexander A. Sherstov (2012). The multiparty communication complexity of set disjointness. In Proceedings of the 44th symposium on Theory of Computing, STOC \u201912, 525\u2013548. ACM, New York, NY, USA. URL http:\/\/doi.acm.org\/10.1145\/2213977.2214026 .","DOI":"10.1145\/2213977.2214026"},{"key":"78_CR52","doi-asserted-by":"crossref","first-page":"255","DOI":"10.26421\/QIC9.3-4-5","volume":"9","author":"Shi Yaoyun","year":"2009","unstructured":"Yaoyun Shi, Zhiqiang Zhang (2009) Communication complexities of symmetric XOR functions. Quantum Information and Computation 9: 255\u2013263","journal-title":"Quantum Information and Computation"},{"key":"78_CR53","unstructured":"Yaoyun Shi & Yufan Zhu (2009). Quantum communication complexity of block-composed functions. Quantum Information and Computation 9, 444\u2013460. URL http:\/\/portal.acm.org\/citation.cfm?id=2011791.2011798 ."},{"key":"78_CR54","doi-asserted-by":"crossref","unstructured":"Ilya D. Shkredov (2006a). On a Generalization of Szemer\u00e9di\u2019s Theorem. Proc. London Math. Soc. 93, 723\u2013760.","DOI":"10.1017\/S0024611506015991"},{"key":"78_CR55","doi-asserted-by":"crossref","unstructured":"Ilya D. Shkredov (2006b). On a problem of Gowers. Izvestiya: Mathematics 70, 385.","DOI":"10.1070\/IM2006v070n02ABEH002316"},{"key":"78_CR56","unstructured":"Victor Shoup (2009). A computational introduction to number theory and algebra. Cambridge University Press."},{"key":"78_CR57","doi-asserted-by":"crossref","unstructured":"Roman Smolensky (1987). Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, STOC \u201987, 77\u201382. ACM, New York, NY, USA. URL http:\/\/doi.acm.org\/10.1145\/28395.28404 .","DOI":"10.1145\/28395.28404"},{"key":"78_CR58","unstructured":"Pascal Tesson (2003). Computational complexity questions related to finite semigroups and monoids. Ph.D. thesis, McGill University."},{"key":"78_CR59","doi-asserted-by":"crossref","unstructured":"Emanuele Viola & Avi Wigderson (2008). Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols. Theory of Computing 4(1), 137\u2013168. URL http:\/\/www.theoryofcomputing.org\/articles\/v004a007 .","DOI":"10.4086\/toc.2008.v004a007"},{"key":"78_CR60","doi-asserted-by":"crossref","unstructured":"Andrew C. Yao (1979). Some complexity questions related to distributive computing (Preliminary Report). In Proceedings of the eleventh annual ACM symposium on Theory of computing, 209\u2013213. ACM Press, New York, NY, USA.","DOI":"10.1145\/800135.804414"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-013-0078-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-013-0078-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-013-0078-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,23]],"date-time":"2022-03-23T04:51:49Z","timestamp":1648011109000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-013-0078-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1,14]]},"references-count":60,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["78"],"URL":"https:\/\/doi.org\/10.1007\/s00037-013-0078-4","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2014,1,14]]}}}