View article

A long-standing open question in the algorithms and complexity literature is whether there exist sorting circuits of size o(n log n). A recent work by Asharov, Lin, and Shi (SODA'21) showed that if the elements to be sorted have short keys whose length k = o(log n), then one can indeed overcome the n log n barrier for sorting circuits, by leveraging non-comparison-based techniques. More specifically, Asharov et al. showed that there exist O(n) · min(k, log n)-sized sorting circuits for k-bit keys, ignoring polylog∗ factors. Interestingly, the recent works by Farhadi et al. (STOC'19) and Asharov et al. (SODA'21) also showed that the above result is essentially optimal for every key length k, assuming that the famous Li-Li network coding conjecture holds. Note also that proving any unconditional super-linear circuit lower bound for a wide class of problems is beyond the reach of current techniques.

Unfortunately, the approach …