2 papers
cs.DS2021
Optimal Sorting Circuits for Short Keys
Wei-Kai Lin, Elaine Shi
A long-standing open question in the algorithms and complexity literature is whether there exist sorting circuits of size . A recent work by Asharov, Lin, and Shi (SOD…
cs.DS2020
Sorting Short Keys in Circuits of Size o(n log n)
Gilad Asharov, Wei-Kai Lin, Elaine Shi
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-sta…