Paper 2018/227

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

Wei-Kai Lin, 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. SODA 2019
Keywords
complexity theoryfoundationsoblivious algorithms
Contact author(s)
wklin @ cs cornell edu
elaine @ cs cornell edu
niconiconi @ sjtu edu cn
History
2018-10-29: last of 5 revisions
2018-03-01: received
See all versions
Short URL
https://ia.cr/2018/227
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/227,
      author = {Wei-Kai Lin and Elaine Shi and Tiancheng Xie},
      title = {Can We Overcome the $n \log n$ Barrier for Oblivious Sorting?},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/227},
      year = {2018},
      url = {https://eprint.iacr.org/2018/227}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.