Welcome to the resource topic for 2018/227
Title:
Can We Overcome the n \log n Barrier for Oblivious Sorting?
Authors: Wei-Kai Lin, Elaine Shi, 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.
ePrint: https://eprint.iacr.org/2018/227
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .