Oblivious Tight Compaction In O(n) Time with Smaller Constant

摘要

Oblivious compaction is a crucial building block for hash-based oblivious RAM. Asharov et al. recently gave a O(n) algorithm for oblivious tight compaction [2]. Their algorithm is deterministic and asymptotically optimal, but the implied constant is ≫2~(111). We give a new algorithm for oblivious tight compaction that runs in time ＜23913.17n + o(n). As part of our construction, we give a new result in the bootstrap percolation of random regular graphs.