Wei-Kai Lin

collaborators

Showing cs.DSShow all

2 papers · 1 filter

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 $o (n lo g n)$ . 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 $n$ elements, where each element is described with a $k$ -bit comparison-key and a $w$ -bit payload. A long-sta…