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 \textit{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 $2\le p$ and $p=o(n^{1/3})$. Our lower bound holds regardless of the number of rounds and local memory size, while for balanced permutation and sorting the upper bound is achieved in a constant number of rounds with load at most $n/p+o(n/p)$. 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 optimal value 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\ge 3$, thus separating 0-1 sorting from general sorting in terms of their communication complexity.
Yuheng Zha, Yilei Wang, Qiyue Gao, Junrong Chen, Yujia Wu, Zhengfeng Lai, Zhengzhong Liu, Eric P. Xing
Humans often solve spatial problems by mentally simulating visual transformations. In contrast, conventional vision-language models (VLMs) reason primarily through language. We investigate whether VLMs can solve spatial problems by reasoning with both text and generated visual states. To this end, we introduce WM-VLM, which equips a pretrained VLM with a lightweight world model branch for generating intermediate visual states. Our two-stage training first teaches the model to generate the next visual state and then to use that state for reasoning. We programmatically construct spatial reasoning tasks with verifiable intermediate visual states. These tasks allow us to evaluate how well the model generates visual states and how much it relies on them to answer the question. On 2D and 3D mental rotation tasks, WM-VLM consistently outperforms the supervised fine-tuned backbone, with gains of up to 39.25 percentage points. Ablations suggest that these gains depend on the generated visual states, as removing or corrupting them sharply reduces performance. Together, these results suggest that internal world models offer a promising path toward VLMs that reason in both language and visual space. Code is publicly available at: https://github.com/yuh-zha/WM-VLM