Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / complexity theory, foundations, oblivious algorithms

Original Publication (with minor differences): SODA 2019

Date: received 24 Feb 2018, last revised 29 Oct 2018

Contact author: wklin at cs cornell edu, elaine at cs cornell edu, niconiconi at sjtu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20181029:173609 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]