Oblivious Parallel Tight Compaction

Wei-Kai Lin

In tight compaction, one is given an array of elements some of which are marked red and the rest are marked blue. The output of the procedure is an array that contains all of the original elements except that now the red ones appear before the blue ones. In other words, tight compaction is equivalent to sorting the array according to 1-bit keys (not necessarily maintaining order within same-key elements). Even its functionality is simple, oblivious tight compaction is an essential building block to other oblivious algorithms, e.g., ORAM, oblivious sorting and permutation.
A recent work of Asharov et al. gives a deterministic tight compaction algorithm that requires worst-case linear amount of work and whose access pattern is oblivious, namely, the access pattern is completely independent of the underlying elements or their assigned colors. In this talk, I will present our parallel tight compaction algorithm with the same features (i.e., it is oblivious, deterministic, and it requires worst-case linear amount of work) except that ours additionally only requires logarithmic parallel depth.

This is a joint work with Gilad Asharov, Ilan Komargodski, and Elaine Shi.