{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:58:56Z","timestamp":1725861536212},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319426334"},{"type":"electronic","value":"9783319426341"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-42634-1_15","type":"book-chapter","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T15:50:21Z","timestamp":1468943421000},"page":"182-193","source":"Crossref","is-referenced-by-count":2,"title":["The Effect of Range and Bandwidth on\u00a0the\u00a0Round Complexity in the Congested Clique Model"],"prefix":"10.1007","author":[{"given":"Florent","family":"Becker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonio Fern\u00e1ndez","family":"Anta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ivan","family":"Rapaport","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"R\u00e9mila","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,20]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Analyzing graph structure via linear measurements. In: Proceedings of SODA 2012, pp. 459\u2013467 (2012)","DOI":"10.1137\/1.9781611973099.40"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: Proceedings of PODS 2012, pp. 5\u201314 (2012)","DOI":"10.1145\/2213556.2213560"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D.: An information statistics approach to data stream and communication complexity. In: Proceedings of FOCS 2002, pp. 209\u2013218 (2002)","DOI":"10.1109\/SFCS.2002.1181944"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Becker, F., Fern\u00e1ndez Anta, A., Rapaport, I., R\u00e9mila, E.: Brief announcement: a hierarchy of congested clique models, from broadcast to unicast. In: Proceedings of PODC 2015, pp. 167\u2013169 (2015)","DOI":"10.1145\/2767386.2767447"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Becker, F., Kosowski, A., Nisse, N., Rapaport, I., Suchan, K.: Allowing each node to communicate only once in a distributed system: shared whiteboard models. In: Proceedings of SPAA 2012, pp. 11\u201317 (2012)","DOI":"10.1145\/2312005.2312008"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Becker, F., Matamala, M., Nisse, N., Rapaport, I., Suchan, K., Todinca, I.: Adding a referee to an interconnection network: what can (not) be computed in one round. In: Proceedings of IPDPS 2011, pp. 508\u2013514 (2011)","DOI":"10.1109\/IPDPS.2011.55"},{"key":"15_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/978-3-319-09620-9_8","volume-title":"Structural Information and Communication Complexity","author":"F Becker","year":"2014","unstructured":"Becker, F., Montealegre, P., Rapaport, I., Todinca, I.: The simultaneous number-in-hand communication model for networks: private coins, public coins and determinism. In: Halld\u00f3rsson, M.M. (ed.) SIROCCO 2014. LNCS, vol. 8576, pp. 83\u201395. Springer, Heidelberg (2014)"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Braverman, M., Ellen, F., Oshman, R., Pitassi, T., Vaikuntanathan, V.: A tight bound for set disjointness in the message-passing model. In: Proceedings of FOCS 2013, pp. 668\u2013677 (2013)","DOI":"10.1109\/FOCS.2013.77"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Braverman, M., Oshman, R.: On information complexity in the broadcast model. In: Proceedings of PODC 2015, pp. 355\u2013364 (2015)","DOI":"10.1145\/2767386.2767425"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Kaski, P., Korhonen, J.H., Lenzen, C., Paz, A., Suomela, J.: Algebraic methods in the congested clique. In: Proceedings of PODC 2015, pp. 143\u2013152","DOI":"10.1145\/2767386.2767414"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Chakrabart, A., Shi, Y., Wirth, A., Yao, A.: Informational complexity and the direct sum problem for simultaneous message complexity. In: Proceedings of FOCS 2001, pp. 270\u2013278. IEEE (2001)","DOI":"10.1109\/SFCS.2001.959901"},{"key":"15_CR12","unstructured":"Chattopadhyay, A., Mukhopadhyay, S.: Tribes is hard in the message passing model. In: Proceedings of STACS 2009, pp. 224\u2013237 (2015)"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Dolev, D., Feder, T.: Multiparty communication complexity. In: Proceedings of FOCS 1989, pp. 428\u2013433 (1989)","DOI":"10.1109\/SFCS.1989.63514"},{"key":"15_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/978-3-642-33651-5_14","volume-title":"Distributed Computing","author":"D Dolev","year":"2012","unstructured":"Dolev, D., Lenzen, C., Peled, S.: \u201cTri, Tri Again\u201d: finding triangles and small subgraphs in a distributed setting. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol. 7611, pp. 195\u2013209. Springer, Heidelberg (2012)"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: Proceedings of PODC 2014, pp. 367\u2013376 (2014)","DOI":"10.1145\/2611462.2611493"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"\u010euri\u0161, P., Rolim, J.D.: Lower bounds on the multiparty communication complexity. J. Comput. Syst. Sci. 56(1), 90\u201395 (1998)","DOI":"10.1006\/jcss.1997.1547"},{"key":"15_CR17","unstructured":"Gronemeier, A.: Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness. In: Proceedings of STACS 2009, pp. 505\u2013516 (2009)"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"Guha, S., McGregor, A., Tench, D.: Vertex and hyperedge connectivity in dynamic graph streams. In: Proceedings of PODS 2015, pp. 241\u2013247 (2015)","DOI":"10.1145\/2745754.2745763"},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"Hegeman, J.W., Pandurangan, G., Pemmaraju, S.V., Sardeshmukh, V.B., Scquizzato, M.: Toward optimal bounds in the congested clique: graph connectivity and MST. In: Proceedings of PODC 2015, pp. 91\u2013100 (2015)","DOI":"10.1145\/2767386.2767434"},{"key":"15_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/978-3-319-09620-9_13","volume-title":"Structural Information and Communication Complexity","author":"JW Hegeman","year":"2014","unstructured":"Hegeman, J.W., Pemmaraju, S.V.: Lessons from the congested clique applied to MapReduce. In: Halld\u00f3rsson, M.M. (ed.) SIROCCO 2014. LNCS, vol. 8576, pp. 149\u2013164. Springer, Heidelberg (2014)"},{"key":"15_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1007\/978-3-662-45174-8_35","volume-title":"Distributed Computing","author":"JW Hegeman","year":"2014","unstructured":"Hegeman, J.W., Pemmaraju, S.V., Sardeshmukh, V.B.: Near-constant-time distributed algorithms on a congested clique. In: Kuhn, F. (ed.) DISC 2014. LNCS, vol. 8784, pp. 514\u2013530. Springer, Heidelberg (2014)"},{"issue":"4","key":"15_CR22","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram, B., Schintger, G.: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math. 5(4), 545\u2013557 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"15_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1007\/978-3-319-25258-2_26","volume-title":"Structural Information and Communication Complexity","author":"J Kari","year":"2015","unstructured":"Kari, J., Matamala, M., Rapaport, I., Salo, V.: Solving the induced subgraph problem in the randomized multiparty simultaneous messages model. In: Scheideler, C. (ed.) SIROCCO 2015. LNCS, vol. 9439, pp. 370\u2013384. Springer, Heidelberg (2015)"},{"key":"15_CR24","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"2006","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (2006)"},{"key":"15_CR25","doi-asserted-by":"crossref","unstructured":"Lenzen, C.: Optimal deterministic routing and sorting on the congested clique. In: Proceedings of PODC 2013, pp. 42\u201350 (2013)","DOI":"10.1145\/2484239.2501983"},{"key":"15_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1007\/978-3-662-45174-8_34","volume-title":"Distributed Computing","author":"Y Li","year":"2014","unstructured":"Li, Y., Sun, X., Wang, C., Woodruff, D.P.: On the communication complexity of linear algebraic problems in the message passing model. In: Kuhn, F. (ed.) DISC 2014. LNCS, vol. 8784, pp. 499\u2013513. Springer, Heidelberg (2014)"},{"key":"15_CR27","doi-asserted-by":"crossref","unstructured":"Lotker, Z., Pavlov, E.: MST construction in $${O}(\\log \\log n)$$ communication rounds. In: Proceedings of SPAA 2003, pp. 94\u2013100 (2003)","DOI":"10.1145\/777412.777428"},{"key":"15_CR28","doi-asserted-by":"crossref","unstructured":"Patt-Shamir, B., Teplitsky, M.: The round complexity of distributed sorting. In: Proceedings of PODC 2011, pp. 249\u2013256 (2011)","DOI":"10.1145\/1993806.1993851"},{"key":"15_CR29","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)"},{"key":"15_CR30","doi-asserted-by":"crossref","unstructured":"Phillips, J.M., Verbin, E., Zhang, Q.: Lower bounds for number-in-hand multi-party communication complexity, made easy. In: Proceedings of SODA 2012, pp. 486\u2013501","DOI":"10.1137\/1.9781611973099.42"},{"key":"15_CR31","doi-asserted-by":"crossref","unstructured":"Woodruff, D.P., Zhang, Q.: An optimal lower bound for distinct elements in the message passing model. In: Proceedings of SODA 2014, pp. 718\u2013733 (2014)","DOI":"10.1137\/1.9781611973402.54"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-42634-1_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T11:03:45Z","timestamp":1568199825000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-42634-1_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319426334","9783319426341"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-42634-1_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}