{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:57Z","timestamp":1781077737438,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":29,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC","award":["759471"],"award-info":[{"award-number":["759471"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316364","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"277-288","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["An optimal space lower bound for approximating MAX-CUT"],"prefix":"10.1145","author":[{"given":"Michael","family":"Kapralov","sequence":"first","affiliation":[{"name":"EPFL, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dmitry","family":"Krachun","sequence":"additional","affiliation":[{"name":"University of Geneva, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Graph sparsification in the semistreaming model","author":"Ahn Kook Jin","year":"2009","unstructured":"{AG09} Kook Jin Ahn and Sudipto Guha . Graph sparsification in the semistreaming model . 2009 . {AG09} Kook Jin Ahn and Sudipto Guha. Graph sparsification in the semistreaming model. 2009."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22012-8_42"},{"key":"e_1_3_2_1_3_1","first-page":"211","volume-title":"Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015","author":"Ahn Kook Jin","year":"2015","unstructured":"{AG15} Kook Jin Ahn and Sudipto Guha . Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. In Guy E. Blelloch and Kunal Agrawal, editors , Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015 , Portland, OR, USA , June 13-15, 2015 , pages 202\u2013 211 . ACM, 2015. {AG15} Kook Jin Ahn and Sudipto Guha. Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. In Guy E. Blelloch and Kunal Agrawal, editors, Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13-15, 2015, pages 202\u2013211. ACM, 2015."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.40"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_3_2_1_6_1","unstructured":"{AKL17} Sepehr Assadi Sanjeev Khanna and Yang Li. On estimating maximum matching size in graph streams. In Philip N. Klein editor Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms 1 At the same time one should note that while the simple intuitive overview of case 1 does not involve external edges they do have an effect on the actual proof \u2013 see Lemmas 7.1 and 7.9 in Section 6 of the full version { KK18 }. The fact that their effect in this case is second order lets us present the simple intuition for case 1 above. SODA 2017 Barcelona Spain Hotel Porta Fira January 16-19 pages 1723\u2013 1742. SIAM 2017.  {AKL17} Sepehr Assadi Sanjeev Khanna and Yang Li. On estimating maximum matching size in graph streams. In Philip N. Klein editor Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms 1 At the same time one should note that while the simple intuitive overview of case 1 does not involve external edges they do have an effect on the actual proof \u2013 see Lemmas 7.1 and 7.9 in Section 6 of the full version { KK18 }. The fact that their effect in this case is second order lets us present the simple intuition for case 1 above. SODA 2017 Barcelona Spain Hotel Porta Fira January 16-19 pages 1723\u2013 1742. SIAM 2017."},{"key":"e_1_3_2_1_7_1","first-page":"1364","volume-title":"Krauthgamer { Kra16 }","author":"Assadi Sepehr","unstructured":"{AKLY16} Sepehr Assadi , Sanjeev Khanna , Yang Li , and Grigory Yaroslavtsev . Maximum matchings in dynamic graph streams and the simultaneous communication model . In Krauthgamer { Kra16 } , pages 1345\u2013 1364 . {AKLY16} Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev. Maximum matchings in dynamic graph streams and the simultaneous communication model. In Krauthgamer { Kra16 }, pages 1345\u20131364."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_3_2_1_9_1","volume-title":"ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings","volume":"9294","author":"Bansal Nikhil","year":"2015","unstructured":"{BF15} Nikhil Bansal and Irene Finocchi , editors. Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings , volume 9294 of Lecture Notes in Computer Science. Springer , 2015 . {BF15} Nikhil Bansal and Irene Finocchi, editors. Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, volume 9294 of Lecture Notes in Computer Science. Springer, 2015."},{"key":"e_1_3_2_1_10_1","first-page":"274","volume-title":"Bansal and Finocchi { BF15 }","author":"Bury Marc","unstructured":"{BS15} Marc Bury and Chris Schwiegelshohn . Sublinear estimation of weighted matchings in dynamic data streams . In Bansal and Finocchi { BF15 } , pages 263\u2013 274 . {CCE + 16} Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, and Sofya Vorotnikova. Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. In Krauthgamer { Kra16 }, pages 1326\u20131344. {BS15} Marc Bury and Chris Schwiegelshohn. Sublinear estimation of weighted matchings in dynamic data streams. In Bansal and Finocchi { BF15 }, pages 263\u2013274. {CCE + 16} Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, and Sofya Vorotnikova. Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. In Krauthgamer { Kra16 }, pages 1326\u20131344."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.81"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/070706550"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.41"},{"key":"e_1_3_2_1_14_1","volume-title":"CCC","author":"Guruswami Venkatesan","year":"2012","unstructured":"{GO12} Venkatesan Guruswami and Krzysztof Onak . Superlinear lower bounds for multipass graph processing . CCC , 2012 . {GO12} Venkatesan Guruswami and Krzysztof Onak. Superlinear lower bounds for multipass graph processing. CCC, 2012."},{"key":"e_1_3_2_1_15_1","volume-title":"STACS","author":"Huang Zengfeng","year":"2015","unstructured":"{HRVZ15} Zengfeng Huang , Bo\u017eidar Radunovi\u0107 , Milan Vojnovi\u0107 , and Qin Zhang . Communication complexity of approximate maximum matching in distributed graph data . STACS , 2015 . {HRVZ15} Zengfeng Huang, Bo\u017eidar Radunovi\u0107, Milan Vojnovi\u0107, and Qin Zhang. Communication complexity of approximate maximum matching in distributed graph data. STACS, 2015."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627938"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688093"},{"key":"e_1_3_2_1_18_1","volume-title":"An optimal space lower bound for approximating MAX-CUT. CoRR, abs\/1811.10879","author":"Kapralov Michael","year":"2018","unstructured":"{KK18} Michael Kapralov and Dmitry Krachun . An optimal space lower bound for approximating MAX-CUT. CoRR, abs\/1811.10879 , 2018 . {KK18} Michael Kapralov and Dmitry Krachun. An optimal space lower bound for approximating MAX-CUT. CoRR, abs\/1811.10879, 2018."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00059"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634129"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.84"},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017","author":"Kapralov Michael","year":"2017","unstructured":"{KKSV17} Michael Kapralov , Sanjeev Khanna , Madhu Sudan , and Ameya Velingker . (1 + \u03a9(1))- Approximation to MAX-CUT requires linear space . In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 , Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1703\u20131722 , 2017 . {KKSV17} Michael Kapralov, Sanjeev Khanna, Madhu Sudan, and Ameya Velingker. (1 + \u03a9(1))-Approximation to MAX-CUT requires linear space. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1703\u20131722, 2017."},{"key":"e_1_3_2_1_23_1","first-page":"451","volume-title":"STACS","author":"Jonathan","year":"2011","unstructured":"{KL11} Jonathan A. Kelner and Alex Levin. Spectral sparsification in the semistreaming setting . STACS , pages 440\u2013 451 , 2011 . {KL11} Jonathan A. Kelner and Alex Levin. Spectral sparsification in the semistreaming setting. STACS, pages 440\u2013451, 2011."},{"key":"e_1_3_2_1_24_1","volume-title":"FOCS","author":"Michael Kapralov KLM","year":"2014","unstructured":"{ KLM + 14} Michael Kapralov , Yin Tat Lee , Cameron Musco , Christopher Musco , and Aaron Sidford . Single pass spectral sparsification in dynamic streams . FOCS , 2014 . {KLM + 14} Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford. Single pass spectral sparsification in dynamic streams. FOCS, 2014."},{"key":"e_1_3_2_1_25_1","volume-title":"Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016","author":"Konrad Christian","year":"2016","unstructured":"{Kon15} Christian Konrad . Maximum matching in turnstile streams. In Bansal and Finocchi { BF15 }, pages 840\u2013852. {Kra16} Robert Krauthgamer, editor . Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 , Arlington, VA, USA , January 10-12, 2016 . SIAM, 2016. {Kon15} Christian Konrad. Maximum matching in turnstile streams. In Bansal and Finocchi { BF15 }, pages 840\u2013852. {Kra16} Robert Krauthgamer, editor. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016. SIAM, 2016."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611497"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.111"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.157"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA","acronym":"STOC '19","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316364","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316364","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316364"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":29,"alternative-id":["10.1145\/3313276.3316364","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316364","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}