View article

We consider the classical problem of sorting an input array containing elements, where each element is described with a -bit comparison key and a -bit payload. A long-standing open problem is whether there exist -sized Boolean circuits for sorting. A landmark result in this area is the work by Ajtai, Komlós, and Szemerédi (An sorting network, STOC'83), where they showed how to achieve sorting circuits with 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 do not exist for general ; 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 barrier when the keys to be sorted are short. Specifically …