Can We Overcome the n log n Barrier for Oblivious Sorting?
Can We Overcome the n log n Barrier for Oblivious Sorting?
复制标题
我们可以克服遗忘排序的 n log n 障碍吗？
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Tiancheng Xie
中科院分区：
文献类型：
--
作者：
Wei;E. Shi;Tiancheng Xie
众所周知，基于非比较的技术可以让我们在随机存取机 (RAM) 上以 o(n log n) 的时间对 n 个元素进行排序。另一方面，（非基于比较的）电路是否可以使用 o(kn log n) 个布尔门对域 [1..2] 中的 n 个元素进行排序，这是一个长期存在的问题。我们考虑这个问题的弱化形式：首先，我们考虑一个受限的排序类别，其中不同键的数量远小于输入长度；其次，我们探索 Oblivious RAM 和概率电路系列，即比电路更强大但比 RAM 弱得多的计算模型。我们证明 Oblivious RAM 和概率电路系列可以在 o(n log n) 时间或 o(kn log n) 电路复杂度内对 o(log n) 位密钥进行排序。我们的算法在不可分割的模型中工作，即它们不仅可以对数字键数组进行排序 - 如果每个键还带有一个不透明的球，我们的算法还可以将球移动到正确的顺序。我们进一步证明，在这样一个不可分割的模型中，不可能在 o(n log n) 时间内对 Ω(log n) 位密钥进行排序，因此 o(log n) 位密钥假设对于克服 n log n 障碍是必要的。最后，在优化 IO 效率之后，我们证明即使是 1 位特殊情况也可以解决开放问题：我们的遗忘算法首次以最佳 IO 效率解决了紧压缩和选择问题。 *这项工作部分得到 NSF 拨款 CNS-1314857、CNS-1514261、CNS-1544613、CNS-1561209、CNS1601879、CNS-1617676、海军研究办公室青年研究员计划奖、Packard 奖学金、DARPA Safeware 拨款（IBM 下的分包商）、斯隆管理学院的资助奖学金、Google 教员研究奖、百度研究奖和 VMWare 研究奖。 †康奈尔大学。 ‡康奈尔大学。 §上海交通大学，访问康奈尔大学期间完成的工作。
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] with o(kn 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(kn log n) circuit complexity. Our algorithms work in the indivisible 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 an indivisible model, it is impossible to sort Ω(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, after optimizing the IO efficiency, we show that even the 1-bit special case can solve open questions: our oblivious algorithms solve tight compaction and selection with optimal IO efficiency for the first time. ∗This work is supported in part by NSF grants CNS-1314857, CNS-1514261, CNS-1544613, CNS-1561209, CNS1601879, CNS-1617676, an Office of Naval Research Young Investigator Program Award, a Packard Fellowship, a DARPA Safeware grant (subcontractor under IBM), a Sloan Fellowship, Google Faculty Research Awards, a Baidu Research Award, and a VMWare Research Award. †Cornell University. ‡Cornell University. §Shanghai Jiao Tong University, work done while visiting Cornell.