{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,7]],"date-time":"2026-09-07T14:20:48Z","timestamp":1788790848339,"version":"build-2803163510"},"reference-count":44,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"Packard Fellowship"},{"DOI":"10.13039\/501100012443","name":"Center for Research in Applied Cryptography and Cyber Security, Bar-Ilan University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100012443","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["891234"],"award-info":[{"award-number":["891234"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["2439\/20"],"award-info":[{"award-number":["2439\/20"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS- 1601879"],"award-info":[{"award-number":["CNS- 1601879"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:p>We consider the classical problem of sorting an input array containing $n$ elements, where each element is described with a $k$-bit comparison key and a $w$-bit payload. A long-standing open problem is whether there exist $(k + w) \\cdot o(n \\log n)$-sized Boolean circuits for sorting. A landmark result in this area is the work by Ajtai, Koml\u00f3s, and Szemer\u00e9di (An $O(n \\log n)$ sorting network, STOC'83), where they showed how to achieve sorting circuits with $(k + w) \\cdot O(n \\log n)$ Boolean gates. The recent work of Farhadi et al. (Lower bounds for external memory integer sorting via network coding, STOC'19) showed that if the famous Li-Li network coding conjecture is true, then sorting circuits of size $w \\cdot o(n \\log n)$ do not exist for general $k$; however, no unconditional lower bound is known (in fact proving superlinear circuit lower bounds in general is out of the reach of existing techniques). In this paper, we show that one can overcome the $n\\log n$ barrier when the keys to be sorted are short. Specifically, we prove that there is a circuit with $(k + w) \\cdot O(n k) \\cdot (\\log^*n - \\log^* (w + k))^{2+\\epsilon}$ Boolean gates capable of sorting any input array containing $n$ elements, each described with a $k$-bit key and a $w$-bit payload. Therefore, if the keys to be sorted are short, say, $k &lt; o(\\log n)$, our result is asymptotically better than the classical Ajtai, Koml\u00f3s, and Szemer\u00e9di sorting network (ignoring ${\\sf poly}\\log^*$ terms); and we also overcome the $n \\log n$ barrier in such cases. Such a result might be surprising initially because it is long known that comparator-based techniques must incur $\\Omega(n \\log n)$ comparator gates even when the keys to be sorted are only 1-bit long (e.g., see Knuth's \u201cArt of Programming\u201d textbook). To the best of our knowledge, we are the first to achieve nontrivial results for sorting circuits using non-comparison-based techniques. We also show that if the Li-Li network coding conjecture is true, our upper bound is optimal, barring ${\\sf poly}\\log^*$ terms, for every $k$ as long as $k = O(\\log n)$.<\/jats:p>","DOI":"10.1137\/20m1380983","type":"journal-article","created":{"date-parts":[[2022,5,5]],"date-time":"2022-05-05T10:42:27Z","timestamp":1651747347000},"page":"424-466","source":"Crossref","is-referenced-by-count":1,"title":["Sorting Short Keys in Circuits of Size ${o(n \\log n)}$"],"prefix":"10.1137","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0846-9773","authenticated-orcid":true,"given":"Gilad","family":"Asharov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wei-Kai","family":"Lin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2022,5,5]]},"reference":[{"key":"atypb1","volume-title":"46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, Patras, Greece, LIPIcs Leibniz Int. Proc. Inform. 132","author":"Afshani P.","year":"2019"},{"key":"atypb2","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1145\/1109557.1109585","volume-title":"Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA '06","author":"Adler M.","year":"2006"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1580"},{"key":"atypb4","first-page":"403","volume-title":"Advances in Cryptology - EUROCRYPT","author":"Asharov G.","year":"2020"},{"key":"atypb5","volume-title":"Proc. Inform. 163","author":"Asharov G.","year":"2020"},{"key":"atypb6","first-page":"1","volume-title":"ACM","author":"Ajtai M.","year":"1983"},{"key":"atypb7","first-page":"99","volume":"5","author":"Alekseev V. E.","year":"1969","journal-title":"Kibernetica"},{"key":"atypb8","first-page":"149","volume-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, ACM","author":"Arora S.","year":"1990"},{"key":"atypb9","first-page":"307","volume-title":"AFIPS Conf. Proc. 32, 1968 Spring Joint Computer Conference","author":"Batcher K. E.","year":"1968"},{"key":"atypb10","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1145\/800152.804904","volume-title":"Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, STOC '72","author":"Blum M.","year":"1972"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80033-9"},{"key":"atypb12","volume-title":"8th Innovations in Theoretical Computer Science Conference, ITCS 2017, Berkeley, CA, LIPIcs Leibniz Int. Proc. Inform. 67","author":"Braverman M.","year":"2017"},{"key":"atypb13","first-page":"50","volume-title":"Proceedings of the Third Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '91","author":"Bast H.","year":"1991"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1159"},{"key":"atypb15","first-page":"357","volume-title":"ACM","author":"Boyle E.","year":"2016"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/0215006"},{"key":"atypb17","unstructured":"S. Dittmer and R. Ostrovsky,\n                      Oblivious tight compaction in O(n) time with smaller constant\n                      , Cryptology ePrint Archive Report 2020\/377, 2020,https:\/\/eprint.iacr.org\/2020\/377."},{"key":"atypb18","first-page":"997","volume-title":"ACM","author":"Farhadi A.","year":"2019"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226670"},{"key":"atypb20","first-page":"684","volume-title":"ACM","author":"Goodrich M. T.","year":"2014"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.09.001"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290675"},{"key":"atypb23","first-page":"135","volume-title":"IEEE Computer Society","author":"Han Y.","year":"2002"},{"key":"atypb24","first-page":"165","volume-title":"ACM","author":"Jimbo S.","year":"1992"},{"key":"atypb25","volume-title":"48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, Glasgow, Scotland, N. Bansal, E. Merelli, and J. Worrell, eds., LIPIcs Leibniz Int. Proc. Inform. 198","author":"Kouck\u00fd M."},{"key":"atypb26","volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"Knuth D. E.","year":"1973"},{"key":"atypb27","first-page":"263","volume":"28","author":"Kirkpatrick D. G.","year":"1983","journal-title":"Comput. Sci."},{"key":"atypb28","volume-title":"Allerton Conference on Communication, Control and Computing","author":"Li Z.","year":"2004"},{"key":"atypb29","first-page":"106","volume-title":"Proceedings of the Seventh Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '95","author":"Leighton T.","year":"1995"},{"key":"atypb30","volume-title":"Optimal sorting circuits for short keys, preprint, arXiv: 2102.11489","author":"Lin W.-K.","year":"2021"},{"key":"atypb31","first-page":"2419","volume-title":"ACM","author":"Lin W.-K.","year":"2019"},{"key":"atypb32","volume-title":"private communication","author":"Maggs B.","year":"2019"},{"key":"atypb33","first-page":"554","volume-title":"LIPIcs Leibniz Int. Proc. Inform. 25","author":"Mitchell J. C.","year":"2014"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840378"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"N. Pippenger,\n                      Selection networks\n                      , in SIGAL International Symposium on Algorithms, Springer, Berlin, 1990, pp. 2-11.","DOI":"10.1007\/3-540-52921-7_50"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0005"},{"key":"atypb37","first-page":"871","volume-title":"FOCS, IEEE","author":"Patel S.","year":"2018"},{"key":"atypb38","first-page":"12","volume-title":"Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '88, ACM","author":"Rosen B. K.","year":"1988"},{"key":"atypb39","volume-title":"Models of Computation: Exploring the Power of Computing","author":"Savage J. E.","year":"1997"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9025-6"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2002.1211"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1137\/0204030"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050049"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1137\/0209043"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1380983","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:12:36Z","timestamp":1787339556000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1380983"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,5]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["10.1137\/20M1380983"],"URL":"https:\/\/doi.org\/10.1137\/20m1380983","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,5]]}}}