{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:53:46Z","timestamp":1744217626071,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2020,2,20]],"date-time":"2020-02-20T00:00:00Z","timestamp":1582156800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,20]],"date-time":"2020-02-20T00:00:00Z","timestamp":1582156800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003399","name":"Science and Technology Commission of Shanghai Municipality","doi-asserted-by":"publisher","award":["17JC1420200"],"award-info":[{"award-number":["17JC1420200"]}],"id":[{"id":"10.13039\/501100003399","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61802069"],"award-info":[{"award-number":["61802069"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1525024, IIS-1633215"],"award-info":[{"award-number":["CCF-1525024, IIS-1633215"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s00446-020-00371-6","type":"journal-article","created":{"date-parts":[[2020,2,20]],"date-time":"2020-02-20T15:02:41Z","timestamp":1582210961000},"page":"515-531","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Communication complexity of approximate maximum matching in the message-passing model"],"prefix":"10.1007","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2671-7483","authenticated-orcid":false,"given":"Zengfeng","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bozidar","family":"Radunovic","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Milan","family":"Vojnovic","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qin","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,20]]},"reference":[{"key":"371_CR1","unstructured":"Ahn, K.J., Guha, S.: Laminar families and metric embeddings: non-bipartite maximum matching problem in the semi-streaming model. CoRR arXiv:1104.4058 (2011)"},{"key":"371_CR2","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.ic.2012.10.006","volume":"222","author":"KJ Ahn","year":"2013","unstructured":"Ahn, K.J., Guha, S.: Linear programming in the semi-streaming model with application to the maximum matching problem. Inf. Comput. 222, 59\u201379 (2013)","journal-title":"Inf. Comput."},{"key":"371_CR3","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Analyzing graph structure via linear measurements. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201912, pp. 459\u2013467 (2012)","DOI":"10.1137\/1.9781611973099.40"},{"key":"371_CR4","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS\u201912, pp. 5\u201314 (2012)","DOI":"10.1145\/2213556.2213560"},{"issue":"1","key":"371_CR5","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Comput. Syst. Sci. 58(1), 137\u2013147 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"371_CR6","doi-asserted-by":"crossref","unstructured":"Alon, N., Nisan, N., Raz, R., Weinstein, O.: Welfare maximization with limited interaction. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1499\u20131512 (2015)","DOI":"10.1109\/FOCS.2015.95"},{"key":"371_CR7","doi-asserted-by":"crossref","unstructured":"Assadi, S., Khanna, S., Li, Y., Yaroslavtsev, G.: Maximum matchings in dynamic graph streams and the simultaneous communication model, chap 93, pp. 1345\u20131364 (2016)","DOI":"10.1137\/1.9781611974331.ch93"},{"issue":"4","key":"371_CR8","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1016\/j.jcss.2003.11.006","volume":"68","author":"Z Bar-Yossef","year":"2004","unstructured":"Bar-Yossef, Z., Jayram, T., Kumar, R., Sivakumar, D.: Special issue on focs 2002 an information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci. 68(4), 702\u2013732 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"371_CR9","doi-asserted-by":"publisher","first-page":"1327","DOI":"10.1137\/100811969","volume":"42","author":"B Barak","year":"2013","unstructured":"Barak, B., Braverman, M., Chen, X., Rao, A.: How to compress interactive communication. SIAM J. Comput. 42(3), 1327\u20131363 (2013)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"371_CR10","doi-asserted-by":"publisher","first-page":"1698","DOI":"10.1137\/130938517","volume":"44","author":"M Braverman","year":"2015","unstructured":"Braverman, M.: Interactive information complexity. SIAM J. Comput. 44(6), 1698\u20131739 (2015)","journal-title":"SIAM J. Comput."},{"key":"371_CR11","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 the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS\u201913, pp. 668\u2013677 (2013)","DOI":"10.1109\/FOCS.2013.77"},{"key":"371_CR12","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A.: Informational complexity and the direct sum problem for simultaneous message complexity. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, FOCS\u201901, pp. 270 (2001)","DOI":"10.1109\/SFCS.2001.959901"},{"key":"371_CR13","volume-title":"Elements of Information Theory","author":"T Cover","year":"2006","unstructured":"Cover, T., Thomas, J.: Elements of Information Theory. Wiley, Hoboken (2006)"},{"key":"371_CR14","doi-asserted-by":"publisher","unstructured":"Dobzinski, S., Nisan, N., Oren, S.: Economic efficiency requires interaction. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC\u201914, pp. 233\u2013242. ACM, New York (2014). https:\/\/doi.org\/10.1145\/2591796.2591815","DOI":"10.1145\/2591796.2591815"},{"issue":"3","key":"371_CR15","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1137\/100801901","volume":"25","author":"L Epstein","year":"2011","unstructured":"Epstein, L., Levin, A., Mestre, J., Segev, D.: Improved approximation guarantees for weighted matching in the semi-streaming model. SIAM J. Discrete Math. 25(3), 1251\u20131265 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"371_CR16","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Sitchinava, N., Zhang, Q.: Sorting, searching, and simulation in the mapreduce framework. In: Algorithms and Computation 7074 of the series Lecture Notes in Computer Science, 374\u2013383 (2011)","DOI":"10.1007\/978-3-642-25591-5_39"},{"issue":"2","key":"371_CR17","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(86)90144-4","volume":"22","author":"A Israeli","year":"1986","unstructured":"Israeli, A., Itai, A.: A fast and simple randomized parallel algorithm for maximal matching. Inf. Process. Lett. 22(2), 77\u201380 (1986)","journal-title":"Inf. Process. Lett."},{"key":"371_CR18","doi-asserted-by":"crossref","unstructured":"Kane, D.M., Nelson, J., Woodruff, D.P.: An optimal algorithm for the distinct elements problem. In: Proceedings of the 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS\u201910, pp. 41\u201352 (2010)","DOI":"10.1145\/1807085.1807094"},{"key":"371_CR19","unstructured":"Kapralov, M.: Better bounds for matchings in the streaming model, chap 121, pp. 1679\u20131697"},{"key":"371_CR20","unstructured":"Kapralov, M., Khanna, S., Sudan, M.: Approximating matching size from random streams, chap 55, pp. 734\u2013751"},{"key":"371_CR21","doi-asserted-by":"crossref","unstructured":"Karloff, H., Suri, S., Vassilvitskii, S.: A model of computation for mapreduce. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201910, pp. 938\u2013948 (2010)","DOI":"10.1137\/1.9781611973075.76"},{"key":"371_CR22","doi-asserted-by":"crossref","unstructured":"Klauck, H., Nanongkai, D., Pandurangan, G., Robinson, P.: The distributed complexity of large-scale graph processing. CoRR arXiv:1311.6209 (2013)","DOI":"10.1137\/1.9781611973730.28"},{"key":"371_CR23","first-page":"840","volume-title":"Maximum Matching in Turnstile Streams","author":"C Konrad","year":"2015","unstructured":"Konrad, C.: Maximum Matching in Turnstile Streams, pp. 840\u2013852. Springer, Berlin (2015)"},{"key":"371_CR24","first-page":"231","volume-title":"Maximum Matching in Semi-streaming with Few Passes","author":"C Konrad","year":"2012","unstructured":"Konrad, C., Magniez, F., Mathieu, C.: Maximum Matching in Semi-streaming with Few Passes, pp. 231\u2013242. Springer, Berlin (2012)"},{"key":"371_CR25","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"key":"371_CR26","doi-asserted-by":"crossref","unstructured":"Lattanzi, S., Moseley, B., Suri, S., Vassilvitskii, S.: Filtering: a method for solving graph problems in mapreduce. In: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA\u201911, pp. 85\u201394 (2011)","DOI":"10.1145\/1989493.1989505"},{"key":"371_CR27","doi-asserted-by":"crossref","unstructured":"Lotker, Z., Patt-Shamir, B., Pettie, S.: Improved distributed approximate matching. In: Proceedings of the 20th Annual Symposium on Parallelism in Algorithms and Architectures, SPAA\u201908, pp. 129\u2013136 (2008)","DOI":"10.1145\/1378533.1378558"},{"key":"371_CR28","doi-asserted-by":"crossref","unstructured":"Lotker, Z., Patt-Shamir, B., Rosen, A.: Distributed approximate matching. In: Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing, PODC\u201907, pp. 167\u2013174 (2007)","DOI":"10.1145\/1281100.1281126"},{"issue":"4","key":"371_CR29","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"371_CR30","first-page":"170","volume-title":"Finding Graph Matchings in Data Streams","author":"A McGregor","year":"2005","unstructured":"McGregor, A.: Finding Graph Matchings in Data Streams, pp. 170\u2013181. Springer, Berlin (2005)"},{"key":"371_CR31","unstructured":"McGregor, A.: Question 16: graph matchings: open problems in data streams and related topics. In: Workshop on Algorithms for Data Streams (2006). http:\/\/www.cse.iitk.ac.in\/users\/sganguly\/data-stream-probs.pdf"},{"issue":"1","key":"371_CR32","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1137\/15M1007525","volume":"45","author":"JM Phillips","year":"2016","unstructured":"Phillips, J.M., Verbin, E., Zhang, Q.: Lower bounds for number-in-hand multiparty communication complexity, made easy. SIAM J. Comput. 45(1), 174\u2013196 (2016)","journal-title":"SIAM J. Comput."},{"key":"371_CR33","first-page":"335","volume-title":"Distributed Weighted Matching","author":"M Wattenhofer","year":"2004","unstructured":"Wattenhofer, M., Wattenhofer, R.: Distributed Weighted Matching, pp. 335\u2013348. Springer, Berlin (2004)"},{"key":"371_CR34","doi-asserted-by":"crossref","unstructured":"Woodruff, D.P., Zhang, Q.: Tight bounds for distributed functional monitoring. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing, STOC\u201912, pp. 941\u2013960 (2012)","DOI":"10.1145\/2213977.2214063"},{"key":"371_CR35","doi-asserted-by":"crossref","unstructured":"Woodruff, D.P., Zhang, Q.: An Optimal Lower Bound for Distinct Elements in the Message Passing Model, chap. 54, pp. 718\u2013733 (2014)","DOI":"10.1137\/1.9781611973402.54"},{"issue":"5","key":"371_CR36","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). https:\/\/doi.org\/10.1007\/s00446-014-0218-3","journal-title":"Distrib. Comput."},{"issue":"1","key":"371_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-010-9438-5","volume":"62","author":"M Zelke","year":"2012","unstructured":"Zelke, M.: Weighted matching in the semi-streaming model. Algorithmica 62(1), 1\u201320 (2012)","journal-title":"Algorithmica"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00371-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-020-00371-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00371-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T19:32:07Z","timestamp":1613763127000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-020-00371-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,20]]},"references-count":37,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["371"],"URL":"https:\/\/doi.org\/10.1007\/s00446-020-00371-6","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2020,2,20]]},"assertion":[{"value":"29 March 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 February 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}