{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:19:21Z","timestamp":1740097161815,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476659"},{"type":"electronic","value":"9783662476666"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47666-6_43","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T07:46:47Z","timestamp":1434700007000},"page":"540-551","source":"Crossref","is-referenced-by-count":7,"title":["The Range of Topological Effects on Communication"],"prefix":"10.1007","author":[{"given":"Arkadev","family":"Chattopadhyay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Atri","family":"Rudra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"43_CR1","unstructured":"Awerbuch, B., Azar, Y.: Buy-at-bulk network design. In: 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, October 19\u201322, Miami Beach, Florida, USA, pp. 542\u2013547 (1997). http:\/\/doi.ieeecomputersociety.org\/10.1109\/SFCS.1997.646143"},{"key":"43_CR2","unstructured":"Balcan, M.F., Blum, A., Fine, S., Mansour, Y.: Distributed learning, communication complexity and privacy. In: COLT, pp. 26.1\u201326.22 (2012)"},{"key":"43_CR3","doi-asserted-by":"crossref","unstructured":"Barak, B., Braverman, M., Chen, X., Rao, A.: How to compress interactive communication. SIAM J. Comput. 42(3), 1327\u20131363 (2013). http:\/\/dx.doi.org\/10.1137\/100811969","DOI":"10.1137\/100811969"},{"key":"43_CR4","doi-asserted-by":"crossref","unstructured":"Beame, P., Koutris, P., Suciu, D.: Communication steps for parallel query processing. In: PODS, pp. 273\u2013284 (2013)","DOI":"10.1145\/2463664.2465224"},{"issue":"1\u20132","key":"43_CR5","first-page":"46","volume":"52","author":"J Bourgain","year":"1995","unstructured":"Bourgain, J.: On lipschitz embedding of finite metric spaces in hilbert space. Israel J. Math. 52(1\u20132), 46\u201352 (1995)","journal-title":"Israel J. Math."},{"key":"43_CR6","unstructured":"Braverman, M., Ellen, F., Oshman, R., Pitassi, T., Vaikuntanathan, V.: A tight bound for set disjointness in the message-passing model. In: 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 668\u2013677 (2013). http:\/\/doi.ieeecomputersociety.org\/10.1109\/FOCS.2013.77"},{"key":"43_CR7","unstructured":"Chattopadhyay, A., Mukhopadhyay, S.: Tribes is hard in the message-passing model. In: STACS, pp. 224\u2013237 (2015)"},{"key":"43_CR8","doi-asserted-by":"crossref","unstructured":"Chattopadhyay, A., Rudra, A.: The Range of Topological Effects on Communication. ArXiv e-prints (April 2015)","DOI":"10.1007\/978-3-662-47666-6_43"},{"key":"43_CR9","doi-asserted-by":"crossref","unstructured":"Chattopadhyay, A., Radhakrishnan, J., Rudra, A.: Topology matters in communication. In: FOCS, pp. 631\u2013640 (2014)","DOI":"10.1109\/FOCS.2014.73"},{"key":"43_CR10","doi-asserted-by":"crossref","unstructured":"Cormode, G.: The continuous distributed monitoring model. SIGMOD Rec. 42(1), 5\u201314 (2013). http:\/\/doi.acm.org\/10.1145\/2481528.2481530","DOI":"10.1145\/2481528.2481530"},{"key":"43_CR11","doi-asserted-by":"crossref","unstructured":"Dolev, D., Feder, T.: Multiparty communication complexity. In: FOCS, pp. 428\u2013433 (1989)","DOI":"10.1109\/SFCS.1989.63514"},{"key":"43_CR12","doi-asserted-by":"crossref","unstructured":"Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: PODC, pp. 367\u2013376 (2014)","DOI":"10.1145\/2611462.2611493"},{"issue":"1","key":"43_CR13","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1006\/jcss.1997.1547","volume":"56","author":"P Duris","year":"1998","unstructured":"Duris, P., Rolim, J.: Lower bounds on the multiparty communication complexity. J. Comput. Syst. Sci. 56(1), 90\u201395 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"43_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1007\/978-3-642-22670-0_22","volume-title":"Studies in Complexity and Cryptography","author":"O Goldreich","year":"2011","unstructured":"Goldreich, O.: Three XOR-Lemmas \u2014 an exposition. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. LNCS, vol. 6650, pp. 248\u2013272. Springer, Heidelberg (2011)"},{"key":"43_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/978-3-642-22670-0_23","volume-title":"Studies in Complexity and Cryptography","author":"O Goldreich","year":"2011","unstructured":"Goldreich, O., Nisan, N., Wigderson, A.: On yao\u2019s XOR-Lemma. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. LNCS, vol. 6650, pp. 273\u2013301. Springer, Heidelberg (2011)"},{"key":"43_CR16","unstructured":"Huang, Z., Radunovic, B., Vojnovic, M., Zhang, Q.: Communication complexity of approximate maximum matching in distributed graph data. In: 32nd Symposium on Theoretical Aspects of Computer Science (STACS), pp. 460\u2013473 (2015)"},{"issue":"3\/4","key":"43_CR17","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF01206317","volume":"5","author":"M Karchmer","year":"1995","unstructured":"Karchmer, M., Raz, R., Wigderson, A.: Super-logarithmic depth lower bounds via the direct sum in communication complexity. Computational Complexity 5(3\/4), 191\u2013204 (1995)","journal-title":"Computational Complexity"},{"key":"43_CR18","doi-asserted-by":"crossref","unstructured":"Karloff, H.J., Suri, S., Vassilvitskii, S.: A model of computation for mapreduce. In: SODA, pp. 938\u2013948 (2010)","DOI":"10.1137\/1.9781611973075.76"},{"issue":"6","key":"43_CR19","doi-asserted-by":"publisher","first-page":"3407","DOI":"10.1109\/TIT.2012.2188883","volume":"58","author":"H Kowshik","year":"2012","unstructured":"Kowshik, H., Kumar, P.: Optimal function computation in directed and undirected graphs. IEEE Transcations on Information Theory 58(6), 3407\u20133418 (2012)","journal-title":"IEEE Transcations on Information Theory"},{"key":"43_CR20","doi-asserted-by":"crossref","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). http:\/\/dx.doi.org\/10.1007\/978-3-662-45174-8_34","DOI":"10.1007\/978-3-662-45174-8_34"},{"issue":"2","key":"43_CR21","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N Linial","year":"1995","unstructured":"Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215\u2013245 (1995)","journal-title":"Combinatorica"},{"key":"43_CR22","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Milkov\u00e1, E., Ne\u0161et\u0159ilov\u00e1, H.: Otakar Boru\u0307vka on minimum spanning tree problem translation of both the 1926 papers, comments, history. Discrete Mathematics 233(13), 3\u201336 (2001). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0012365X00002247 ; czech and Slovak 2","DOI":"10.1016\/S0012-365X(00)00224-7"},{"key":"43_CR23","unstructured":"Phillips, J.M., Verbin, E., Zhang, Q.: Lower bounds for number-in-hand multiparty communication complexity, made easy. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 486\u2013501 (2012). http:\/\/portal.acm.org\/citation.cfm?id=2095158&CFID=63838676&CFTOKEN=79617016"},{"issue":"3","key":"43_CR24","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/s004930050062","volume":"19","author":"R Raz","year":"1999","unstructured":"Raz, R., McKenzie, P.: Separation of the monotone $$\\text{NC}$$ hierarchy. Combinatorica 19(3), 403\u2013435 (1999)","journal-title":"Combinatorica"},{"issue":"6","key":"43_CR25","doi-asserted-by":"publisher","first-page":"2113","DOI":"10.1137\/08071421X","volume":"38","author":"A Sherstov","year":"2009","unstructured":"Sherstov, A.: Separating $$\\text{AC}^0$$ from depth-2 majority circuits. SIAM J. Comput. 38(6), 2113\u20132129 (2009)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"43_CR26","doi-asserted-by":"crossref","first-page":"444","DOI":"10.26421\/QIC9.5-6-7","volume":"9","author":"Y Shi","year":"2009","unstructured":"Shi, Y., Zhu, Y.: Quantum communication complexity of block-composed functions. Qunatum Computation and Information 9(5), 444\u2013460 (2009)","journal-title":"Qunatum Computation and Information"},{"issue":"4","key":"43_CR27","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1145\/31846.32978","volume":"34","author":"P Tiwari","year":"1987","unstructured":"Tiwari, P.: Lower bounds on communication complexity in distributed computer networks. J. ACM 34(4), 921\u2013938 (1987)","journal-title":"J. ACM"},{"issue":"8","key":"43_CR28","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"LG Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103\u2013111 (1990)","journal-title":"Commun. ACM"},{"key":"43_CR29","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer-Verlag New York Inc., New York (2001)"},{"key":"43_CR30","doi-asserted-by":"crossref","unstructured":"Woodruff, D., Zhang, Q.: Tight bounds for distributed functional monitoring. In: STOC, pp. 941\u2013960 (2012)","DOI":"10.1145\/2213977.2214063"},{"key":"43_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-642-41527-2_2","volume-title":"Distributed Computing","author":"DP Woodruff","year":"2013","unstructured":"Woodruff, D.P., Zhang, Q.: When distributed computation is communication expensive. In: Afek, Y. (ed.) DISC 2013. LNCS, vol. 8205, pp. 16\u201330. Springer, Heidelberg (2013)"},{"key":"43_CR32","doi-asserted-by":"crossref","unstructured":"Woodruff, D., Zhang, Q.: An optimal lower bound for distinct elements in the message passing model. In: SODA, pp. 718\u2013733 (2014)","DOI":"10.1137\/1.9781611973402.54"},{"key":"43_CR33","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Some complexity questions related to distributed computing. In: 11th ACM Symposium on Theory of Computing (STOC), pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47666-6_43","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,14]],"date-time":"2022-05-14T05:24:29Z","timestamp":1652505869000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-47666-6_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476659","9783662476666"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47666-6_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}