**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@cs cornell edu,niconiconi@sjtu edu cn

**Available format(s): **PDF | BibTeX Citation

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

**Short URL: **ia.cr/2018/227

[ Cryptology ePrint archive ]