Oblivious Tight Compaction In O(n) Time with Smaller Constant
Samuel Dittmer, Rafail Ostrovsky
Abstract:
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 \({\gg }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.
comment:
SCN 2020: 253-274
Fetch PDF file of the paper