{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T16:12:06Z","timestamp":1787760726728,"version":"build-2784847793"},"publisher-location":"New York, NY, USA","reference-count":21,"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":"NSF AF:Medium","award":["CCF-1161365"],"award-info":[{"award-number":["CCF-1161365"]}]},{"name":"UMD AI in Business and Society Seed Grant"},{"name":"NSF SPX","award":["CCF-1822738"],"award-info":[{"award-number":["CCF-1822738"]}]},{"name":"NSF BIGDATA","award":["IIS-1546108"],"award-info":[{"award-number":["IIS-1546108"]}]},{"name":"AUFF Starting Grant"},{"name":"NSF Career","award":["CCF-1053605"],"award-info":[{"award-number":["CCF-1053605"]}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF1822805"],"award-info":[{"award-number":["CCF1822805"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"UMD Year of Data Science Program Grant"},{"name":"Villum Young Investigator"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316337","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T08:19:08Z","timestamp":1561018748000},"page":"997-1008","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Lower bounds for external memory integer sorting via network coding"],"prefix":"10.1145","author":[{"given":"Alireza","family":"Farhadi","sequence":"first","affiliation":[{"name":"University of Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[{"name":"University of Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kasper Green","family":"Larsen","sequence":"additional","affiliation":[{"name":"Aarhus University, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[{"name":"Cornell University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109585"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.850663"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806701"},{"key":"e_1_3_2_1_5_1","volume-title":"8th Innovations in Theoretical Computer Science Conference, ITCS 2017","author":"Braverman M.","year":"2017","unstructured":"M. Braverman , S. Garg , and A. Schvartzman . Coding in undirected graphs is either very helpful or not helpful at all . In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017 , January 9-11, 2017 , Berkeley, CA, USA, pages 18:1\u2013 18:18 , 2017. M. Braverman, S. Garg, and A. Schvartzman. Coding in undirected graphs is either very helpful or not helpful at all. In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, pages 18:1\u2013 18:18, 2017."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055437"},{"key":"e_1_3_2_1_7_1","volume-title":"Lower bounds for external memory integer sorting via network coding. CoRR, abs\/1811.01313","author":"Farhadi A.","year":"2018","unstructured":"A. Farhadi , M. Hajiaghayi , K. G. Larsen , and E. Shi . Lower bounds for external memory integer sorting via network coding. CoRR, abs\/1811.01313 , 2018 . A. Farhadi, M. Hajiaghayi, K. G. Larsen, and E. Shi. Lower bounds for external memory integer sorting via network coding. CoRR, abs\/1811.01313, 2018."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509993"},{"key":"e_1_3_2_1_9_1","first-page":"144","volume-title":"Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on","author":"Han Y.","unstructured":"Y. Han and M. Thorup . Integer sorting in O (nplg lg n) expected time and linear space . In Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on , pages 135\u2013 144 . IEEE, 2002. Y. Han and M. Thorup. Integer sorting in O (nplg lg n) expected time and linear space. In Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on, pages 135\u2013144. IEEE, 2002."},{"key":"e_1_3_2_1_10_1","volume-title":"On the capacity of information networks","author":"Harvey N. J.","year":"2006","unstructured":"N. J. Harvey , R. Kleinberg , and A. R. Lehman . On the capacity of information networks . IEEE\/ACM Transactions on Networking (TON) , 14(SI):2345\u20132364, 2006 . N. J. Harvey, R. Kleinberg, and A. R. Lehman. On the capacity of information networks. IEEE\/ACM Transactions on Networking (TON), 14(SI):2345\u20132364, 2006."},{"key":"e_1_3_2_1_11_1","volume-title":"Comparing network coding with multicommodity flow for the k-pairs communication problem","author":"Harvey N. J.","year":"2004","unstructured":"N. J. Harvey , R. D. Kleinberg , and A. R. Lehman . Comparing network coding with multicommodity flow for the k-pairs communication problem . 2004 . N. J. Harvey, R. D. Kleinberg, and A. R. Lehman. Comparing network coding with multicommodity flow for the k-pairs communication problem. 2004."},{"key":"e_1_3_2_1_12_1","first-page":"582","volume-title":"Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms","author":"Iacono J.","unstructured":"J. Iacono and M. P\u0103tra\u015fcu . Using hashing to solve the dictionary problem (in external memory) . In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms , pages 570\u2013 582 . SIAM, 2012. J. Iacono and M. P\u0103tra\u015fcu. Using hashing to solve the dictionary problem (in external memory). In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms, pages 570\u2013582. SIAM, 2012."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.874543"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.81"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2003.818197"},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of the 42nd Allerton Annual Conference on Communication, Control and Computing, Allerton\u201904","author":"Li Z.","year":"2004","unstructured":"Z. Li and B. Li . Network coding: the case of multiple unicast sessions . In Proceedings of the 42nd Allerton Annual Conference on Communication, Control and Computing, Allerton\u201904 , 2004 . Z. Li and B. Li. Network coding: the case of multiple unicast sessions. In Proceedings of the 42nd Allerton Annual Conference on Communication, Control and Computing, Allerton\u201904, 2004."},{"key":"e_1_3_2_1_17_1","first-page":"2194","volume-title":"INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE","volume":"3","author":"Li Z.","unstructured":"Z. Li , B. Li , D. Jiang , and L. C. Lau . On achieving optimal throughput with network coding . In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE , volume 3 , pages 2184\u2013 2194 . IEEE, 2005. Z. Li, B. Li, D. Jiang, and L. C. Lau. On achieving optimal throughput with network coding. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, volume 3, pages 2184\u20132194. IEEE, 2005."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/110842211"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322274"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873613"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2771738"}],"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.3316337","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316337","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316337","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:54:32Z","timestamp":1750190072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316337"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":21,"alternative-id":["10.1145\/3313276.3316337","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316337","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"}}]}}