Linear-sized circuits for compaction and selection
Speaker
Host
Prof. Srini Devadas
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 bit-length w;
2) compaction, i.e., sorting an array of n elements each with a 1-bit key and a w-bit 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 non-trivial, non-comparison-based 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 n-bits, our circuit size is asymptotically better than AKS.
Results of such nature are long known to be impossible (see [Knuth'73]) in the comparator-based model which is adopted by known sorting networks; and we are the first to show non-trivial, non-comparison-based results in the circuit model of computation.
Finally, I will briefly comment on the relations of this result to constructing optimal ORAM.
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 bit-length w;
2) compaction, i.e., sorting an array of n elements each with a 1-bit key and a w-bit 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 non-trivial, non-comparison-based 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 n-bits, our circuit size is asymptotically better than AKS.
Results of such nature are long known to be impossible (see [Knuth'73]) in the comparator-based model which is adopted by known sorting networks; and we are the first to show non-trivial, non-comparison-based results in the circuit model of computation.
Finally, I will briefly comment on the relations of this result to constructing optimal ORAM.