{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:06:51Z","timestamp":1757617611789,"version":"3.44.0"},"publisher-location":"Singapore","reference-count":33,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819610891"},{"type":"electronic","value":"9789819610907"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-981-96-1090-7_40","type":"book-chapter","created":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T16:33:24Z","timestamp":1741106004000},"page":"494-504","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Communication Complexity of\u00a0Distributed Maximization"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-1933-1538","authenticated-orcid":false,"given":"Yuxiang","family":"Tian","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0002-5587-4752","authenticated-orcid":false,"given":"Xiaoyi","family":"Zhu","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2671-7483","authenticated-orcid":false,"given":"Zengfeng","family":"Huang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,3,5]]},"reference":[{"key":"40_CR1","unstructured":"Armbrust, M., et\u00a0al.: Above the clouds: A berkeley view of cloud computing. Tech. rep., Technical Report UCB\/EECS-2009-28, EECS Department, University of California\u00a0$$\\ldots $$ (2009)"},{"key":"40_CR2","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: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 668\u2013677. IEEE (2013)","DOI":"10.1109\/FOCS.2013.77"},{"key":"40_CR3","doi-asserted-by":"crossref","unstructured":"Braverman, M., Oshman, R.: On information complexity in the broadcast model. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pp. 355\u2013364 (2015)","DOI":"10.1145\/2767386.2767425"},{"key":"40_CR4","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1007\/s00453-015-0093-8","volume":"76","author":"M Braverman","year":"2016","unstructured":"Braverman, M., Weinstein, O.: A discrepancy lower bound for information complexity. Algorithmica 76, 846\u2013864 (2016)","journal-title":"Algorithmica"},{"key":"40_CR5","doi-asserted-by":"crossref","unstructured":"Brody, J., Chakrabarti, A., Kondapally, R., Woodruff, D.P., Yaroslavtsev, G.: Beyond set disjointness: the communication complexity of finding the intersection. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, pp. 106\u2013113 (2014)","DOI":"10.1145\/2611462.2611501"},{"key":"40_CR6","doi-asserted-by":"crossref","unstructured":"Cao, P., Wang, Z.: Efficient top-k query calculation in distributed networks. In: Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, pp. 206\u2013215 (2004)","DOI":"10.1145\/1011767.1011798"},{"key":"40_CR7","unstructured":"Christidis, P., Rivas, J.N.I., et\u00a0al.: Measuring road congestion. Institute for Prospective Technological Studies (IPTS), European Commission Joint Research Centre. Retrieved from http:\/\/ipts.jrc.ec.europa.eu\/publications\/pub.cfm (2012)"},{"issue":"1","key":"40_CR8","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/2481528.2481530","volume":"42","author":"G Cormode","year":"2013","unstructured":"Cormode, G.: The continuous distributed monitoring model. ACM SIGMOD Rec. 42(1), 5\u201314 (2013)","journal-title":"ACM SIGMOD Rec."},{"issue":"2","key":"40_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1921659.1921667","volume":"7","author":"G Cormode","year":"2011","unstructured":"Cormode, G., Muthukrishnan, S., Yi, K.: Algorithms for distributed functional monitoring. ACM Trans. Algorithms (TALG) 7(2), 1\u201320 (2011)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"40_CR10","doi-asserted-by":"crossref","unstructured":"Cormode, G., Muthukrishnan, S., Yi, K., Zhang, Q.: Optimal sampling from distributed streams. In: Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 77\u201386 (2010)","DOI":"10.1145\/1807085.1807099"},{"key":"40_CR11","doi-asserted-by":"crossref","unstructured":"Dolev, D., Feder, T.: Multiparty communication complexity. IBM Thomas J, Watson Research Division (1989)","DOI":"10.1109\/SFCS.1989.63514"},{"key":"40_CR12","doi-asserted-by":"crossref","unstructured":"El-Sayed, H., et al.: Edge of things: the big picture on the integration of edge, IoT and the cloud in a distributed computing environment. IEEE Access 6, 1706\u20131717 (2017)","DOI":"10.1109\/ACCESS.2017.2780087"},{"key":"40_CR13","doi-asserted-by":"crossref","unstructured":"Huang, Z., Yi, K., Liu, Y., Chen, G.: Optimal sampling algorithms for frequency estimation in distributed data. In: 2011 Proceedings IEEE INFOCOM, pp. 1997\u20132005. IEEE (2011)","DOI":"10.1109\/INFCOM.2011.5935005"},{"key":"40_CR14","doi-asserted-by":"crossref","unstructured":"Huang, Z., Yi, K., Zhang, Q.: Randomized algorithms for tracking distributed count, frequencies, and ranks. In: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 295\u2013306 (2012)","DOI":"10.1145\/2213556.2213596"},{"key":"40_CR15","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Williams, R.: Communication complexity with synchronized clocks. In: 2010 IEEE 25th Annual Conference on Computational Complexity, pp. 259\u2013269. IEEE (2010)","DOI":"10.1109\/CCC.2010.32"},{"key":"40_CR16","doi-asserted-by":"crossref","unstructured":"Juang, P., Oki, H., Wang, Y., Martonosi, M., Peh, L.S., Rubenstein, D.: Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet. In: Proceedings of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 96\u2013107 (2002)","DOI":"10.1145\/605397.605408"},{"issue":"5","key":"40_CR17","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/1629607.1629613","volume":"39","author":"BM Leiner","year":"2009","unstructured":"Leiner, B.M., et al.: A brief history of the internet. ACM SIGCOMM Comput. Commun. Rev. 39(5), 22\u201331 (2009)","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"issue":"8","key":"40_CR18","doi-asserted-by":"publisher","first-page":"1859","DOI":"10.1007\/s00607-020-00900-y","volume":"103","author":"D Lindsay","year":"2021","unstructured":"Lindsay, D., Gill, S.S., Smirnova, D., Garraghan, P.: The evolution of distributed computing systems: from fundamental to new frontiers. Computing 103(8), 1859\u20131878 (2021)","journal-title":"Computing"},{"key":"40_CR19","unstructured":"Michel, S., Triantafillou, P., Weikum, G.: KLEE: a framework for distributed top-k query algorithms. In: Proceedings of the 31st International Conference on Very Large Data Bases, pp. 637\u2013648. Citeseer (2005)"},{"issue":"19","key":"40_CR20","doi-asserted-by":"publisher","first-page":"209","DOI":"10.3182\/20100913-2-FR-4014.00057","volume":"43","author":"Y Mo","year":"2010","unstructured":"Mo, Y., Sinopoli, B.: Communication complexity and energy efficient consensus algorithm. IFAC Proc. Volumes 43(19), 209\u2013214 (2010)","journal-title":"IFAC Proc. Volumes"},{"key":"40_CR21","doi-asserted-by":"publisher","first-page":"47980","DOI":"10.1109\/ACCESS.2018.2866491","volume":"6","author":"RK Naha","year":"2018","unstructured":"Naha, R.K., et al.: Fog computing: survey of trends, architectures, requirements, and research directions. IEEE Access 6, 47980\u201348009 (2018)","journal-title":"IEEE Access"},{"key":"40_CR22","first-page":"301","volume":"1","author":"N Nisan","year":"1993","unstructured":"Nisan, N.: The communication complexity of threshold gates. Comb. Paul Erdos Eighty 1, 301\u2013315 (1993)","journal-title":"Comb. Paul Erdos Eighty"},{"key":"40_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00446-008-0055-3","volume":"21","author":"B Patt-Shamir","year":"2008","unstructured":"Patt-Shamir, B., Shafrir, A.: Approximate distributed top-k queries. Distrib. Comput. 21, 1\u201322 (2008)","journal-title":"Distrib. Comput."},{"key":"40_CR24","doi-asserted-by":"crossref","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, pp. 486\u2013501. SIAM (2012)","DOI":"10.1137\/1.9781611973099.42"},{"key":"40_CR25","doi-asserted-by":"crossref","unstructured":"Ramamoorthy, S.N., Sinha, M.: On the communication complexity of greater-than. In: Allerton, pp. 442\u2013444 (2015)","DOI":"10.1109\/ALLERTON.2015.7447037"},{"issue":"2","key":"40_CR26","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.tranpol.2003.09.002","volume":"11","author":"PR Stopher","year":"2004","unstructured":"Stopher, P.R.: Reducing road congestion: a reality check. Transp. Policy 11(2), 117\u2013131 (2004)","journal-title":"Transp. Policy"},{"key":"40_CR27","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1007\/s00493-014-3078-3","volume":"35","author":"E Viola","year":"2015","unstructured":"Viola, E.: The communication complexity of addition. Combinatorica 35, 703\u2013747 (2015)","journal-title":"Combinatorica"},{"key":"40_CR28","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 the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 718\u2013733. SIAM (2014)","DOI":"10.1137\/1.9781611973402.54"},{"issue":"5","key":"40_CR29","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/s00446-014-0218-3","volume":"30","author":"DP Woodruff","year":"2017","unstructured":"Woodruff, D.P., Zhang, Q.: When distributed computation is communication expensive. Distrib. Comput. 30(5), 309\u2013323 (2017)","journal-title":"Distrib. Comput."},{"key":"40_CR30","doi-asserted-by":"crossref","unstructured":"Wu, H., Gan, J., Zhang, R.: Learning based distributed tracking. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2040\u20132050 (2020)","DOI":"10.1145\/3394486.3403255"},{"key":"40_CR31","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Some complexity questions related to distributive computing (preliminary report). In: Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"},{"key":"40_CR32","doi-asserted-by":"crossref","unstructured":"Yi, K., Zhang, Q.: Optimal tracking of distributed heavy hitters and quantiles. In: Proceedings of the Twenty-Eighth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 167\u2013174 (2009)","DOI":"10.1145\/1559795.1559820"},{"key":"40_CR33","doi-asserted-by":"crossref","unstructured":"Zhao, Q., Ogihara, M., Wang, H., Xu, J.: Finding global icebergs over distributed data sets. In: Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 298\u2013307 (2006)","DOI":"10.1145\/1142351.1142394"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-1090-7_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T07:04:04Z","timestamp":1757142244000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-1090-7_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819610891","9789819610907"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-1090-7_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"5 March 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shanghai","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/anl.sjtu.edu.cn\/cocoon2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}