Communication-Oblivious Permutation and Sorting

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


MPhil Thesis Defence


Title: "Communication-Oblivious Permutation and Sorting"

By

Mr. Qi DONG


Abstract:

With the help of secure hardware such as trusted execution environments
(TEEs), private data can be uploaded and computed in untrusted cloud
clusters, so that an adversary controlling the cloud can only see the
data in encrypted form. However, the communication pattern between the
processors may still reveal sensitive information about the data, so it is
important to develop parallel algorithms in the BSP model whose
communication pattern is independent of the input data, a property known
as communication obliviousness. In this paper, we study such algorithms
for three fundamental problems: permutation, sorting, and 0-1 sorting.
For the first two problems, we prove a tight (up to lower-order terms)
communication complexity of $(2-2/p)n\pm o(n)$. Here, $p$ is the number
of processors and $n$ is the input size, assuming the parameter regime
$2\le p≤\tilde{o}(n^{1/4})$. Our lower bound holds regardless of the
number of rounds and local memory size, while the upper bound can be
achieved in a constant number of rounds with $n/p+o(n/p)$ local memory
per processor. For 0-1 sorting, we also derive a tight communication
complexity of $C_{\mathrm{cut}}(p)\cdot n\pm o(n)$, where $C_{\mathrm{cut}}(p)$
is the optimum of a linear program parameterized by $p$. Although there
appears to be no closed-form for $C_{\mathrm{cut}}(p)$, we show that it is
strictly smaller than $2-2/p$ for all $p\ge3$, thus separating 0-1
sorting from general sorting in terms of their communication complexity.


Date:                   Thursday, 20 August 2026

Time:                   10:00am - 12:00noon

Venue:                  Room 3494
                        Lifts 25-26

Chairman:               Dr. Sunil ARYA

Committee Members:      Prof. Ke YI (Supervisor)
                        Dr. Mingxun ZHOU