{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:41Z","timestamp":1750220621151,"version":"3.41.0"},"reference-count":7,"publisher":"Association for Computing Machinery (ACM)","issue":"10","license":[{"start":{"date-parts":[[2020,9,23]],"date-time":"2020-09-23T00:00:00Z","timestamp":1600819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2020,9,23]]},"abstract":"<jats:p>\n            Sorting extremely large datasets is a frequently occurring task in practice. These datasets are usually much larger than the computer's main memory; thus, external memory sorting algorithms, first introduced by Aggarwal and Vitter, are often used. The complexity of comparison-based external memory sorting has been understood for decades by now; however, the situation remains elusive if we assume the keys to be sorted are integers. In internal memory, one can sort a set of\n            <jats:italic>n<\/jats:italic>\n            integer keys of \u0398(lg\n            <jats:italic>n<\/jats:italic>\n            ) bits each in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) time using the classic Radix Sort algorithm; however, in external memory, there are no faster integer sorting algorithms known than the simple comparison-based ones. Whether such algorithms exist has remained a central open problem in external memory algorithms for more than three decades.\n          <\/jats:p>\n          <jats:p>\n            In this paper, we present a\n            <jats:italic>tight<\/jats:italic>\n            conditional lower bound on the complexity of external memory sorting of integers. Our lower bound is based on a famous conjecture in network coding by Li and Li, who conjectured that network coding cannot help anything beyond the standard multicommodity flow rate in undirected graphs.\n          <\/jats:p>\n          <jats:p>\n            The only previous work connecting the Li and Li conjecture to lower bounds for algorithms is due to Adler et al. Adler et al. indeed obtain relatively simple lower bounds for\n            <jats:italic>oblivious<\/jats:italic>\n            algorithms (the memory access pattern is fixed and independent of the input data). Unfortunately, obliviousness is a strong limitation, especially for integer sorting: we show that the Li and Li conjecture implies an \u03a9(\n            <jats:italic>n<\/jats:italic>\n            lg\n            <jats:italic>n<\/jats:italic>\n            ) lower bound for internal memory\n            <jats:italic>oblivious<\/jats:italic>\n            sorting when the keys are \u0398(lg\n            <jats:italic>n<\/jats:italic>\n            ) bits. This is in sharp contrast to the classic (nonoblivious) Radix Sort algorithm. Indeed, going beyond obliviousness is highly nontrivial; we need to introduce several new methods and involved techniques, which are of their own interest, to obtain our tight lower bound for external memory integer sorting.\n          <\/jats:p>","DOI":"10.1145\/3416268","type":"journal-article","created":{"date-parts":[[2020,9,23]],"date-time":"2020-09-23T14:26:49Z","timestamp":1600871209000},"page":"97-105","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Lower bounds for external memory integer sorting via network coding"],"prefix":"10.1145","volume":"63","author":[{"given":"Alireza","family":"Farhadi","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, MD"}]},{"given":"Mohammad Taghi","family":"Hajiaghayi","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD"}]},{"given":"Kasper Green","family":"Larsen","sequence":"additional","affiliation":[{"name":"Aarhus University, Denmark"}]},{"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY"}]}],"member":"320","published-online":{"date-parts":[[2020,9,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109585"},{"key":"e_1_2_1_2_1","first-page":"31","article-title":"complexity of sorting and related problems","volume":"9","author":"Aggarwal A.","year":"1988","unstructured":"Aggarwal , A. , Vitter , J. The input\/output complexity of sorting and related problems . Commun. ACM 9 , 31 ( 1988 ), 1116--1127. Aggarwal, A., Vitter, J. The input\/output complexity of sorting and related problems. Commun. ACM 9, 31 (1988), 1116--1127.","journal-title":"Commun. ACM"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806701"},{"key":"e_1_2_1_4_1","volume-title":"8th Innovations in Theoretical Computer Science Conference, ITCS 2017","author":"Braverman M.","year":"2017","unstructured":"Braverman , M. , Garg , S. , Schvartzman , A. 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 (2017), 18:1--18:18. Braverman, M., Garg, S., Schvartzman, A. 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 (2017), 18:1--18:18."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509993"},{"volume-title":"Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science","year":"2002","key":"e_1_2_1_6_1","unstructured":"Han, Y., Thorup, M. Integer sorting [EQUATION - please see PDF] expected time and linear space . In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science ( 2002 ), IEEE, 135--144. Han, Y., Thorup, M. Integer sorting [EQUATION - please see PDF] expected time and linear space. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (2002), IEEE, 135--144."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 42nd Allerton Annual Conference on Communication, Control and Computing, Allerton '04","author":"Li Z.","year":"2004","unstructured":"Li , Z. , Li , B. Network coding: the case of multiple unicast sessions . In Proceedings of the 42nd Allerton Annual Conference on Communication, Control and Computing, Allerton '04 ( 2004 ). Li, Z., Li, B. Network coding: the case of multiple unicast sessions. In Proceedings of the 42nd Allerton Annual Conference on Communication, Control and Computing, Allerton '04 (2004)."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3416268","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3416268","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:21Z","timestamp":1750197681000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3416268"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,23]]},"references-count":7,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,9,23]]}},"alternative-id":["10.1145\/3416268"],"URL":"https:\/\/doi.org\/10.1145\/3416268","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2020,9,23]]},"assertion":[{"value":"2020-09-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}