Linearsized circuits for compaction and selection
Elaine Shi (Cornell University)
Abstract:
In this talk, I will describe how to construct an O(n w (polylog* n  polylog* w))sized circuit for solving
1) selection, i.e., finding the median of n elements each of bitlength w;
2) compaction, i.e., sorting an array of n elements each with a 1bit key and a wbit payload.
For w >= log^{(c)} n where log^{(c)} denotes taking iterative logarithm any constant number of times, the circuit size is strictly linear and optimal, i.e., O(nw).
We also show a nontrivial, noncomparisonbased generalization of the AKS sorting network: sorting n elements each of w bits requires a circuit of O(n w log K) size (ignoring polylog* factors) assuming each element's key comes from [K]. For keys much shorter than log nbits, our circuit size is asymptotically better than AKS.
Results of such nature are long known to be impossible (see [Knuth'73]) in the comparatorbased model which is adopted by known sorting networks; and we are the first to show nontrivial, noncomparisonbased results in the circuit model of computation.
Finally, I will briefly comment on the relations of this result to constructing optimal ORAM.
