Paper 2018/227

Can We Overcome the $n \log n$ Barrier for Oblivious Sorting?

Wei-Kai Lin and Elaine Shi and Tiancheng Xie

Abstract

It is well-known that non-comparison-based techniques can allow us to sort $n$ elements in $o(n \log n)$ time on a Random-Access Machine (RAM). On the other hand, it is a long-standing open question whether (non-comparison-based) circuits can sort $n$ elements from the domain $[1..2^k]$ with $o(k n \log n)$ boolean gates. We consider weakened forms of this question: first, we consider a restricted class of sorting where the number of distinct keys is much smaller than the input length; and second, we explore Oblivious RAMs and probabilistic circuit families, i.e., computational models that are somewhat more powerful than circuits but much weaker than RAM. We show that Oblivious RAMs and probabilistic circuit families can sort $o(\log n)$-bit keys in $o(n \log n)$ time or $o(k n \log n)$ circuit complexity where $n$ is the input length. Our algorithms work in the balls-and-bins model, i.e., not only can they sort an array of numerical keys --- if each key additionally carries an opaque ball, our algorithms can also move the balls into the correct order. We further show that in such a balls-and-bins model, it is impossible to sort $\Omega(\log n)$-bit keys in $o(n \log n)$ time, and thus the $o(\log n)$-bit-key assumption is necessary for overcoming the $n \log n$ barrier. Finally, we optimize the IO efficiency of our oblivious algorithms for RAMs --- we show that even the $1$-bit special case of our algorithm can solve open questions regarding whether there exist oblivious algorithms for tight compaction and selection in linear IO.