# Pure and Applied Mathematics Quarterly

## Volume 18 (2022)

### Special issue in honor of Fan Chung

Guest editors: Paul Horn, Yong Lin, and Linyuan Lu

### On the generalized shuffle-exchange problem

Pages: 2619 – 2645

DOI: https://dx.doi.org/10.4310/PAMQ.2022.v18.n6.a13

#### Authors

Xiaoming Sun (State Key Lab of Processors, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China; and University of the Chinese Academy of Sciences, Beijing, China)

Yuan Sun (State Key Lab of Processors, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China; and University of the Chinese Academy of Sciences, Beijing, China)

Kewen Wu (University of California, Berkeley, Calif., U.S.A.)

Zhiyu Xia (State Key Lab of Processors, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China; and University of the Chinese Academy of Sciences, Beijing, China)

#### Abstract

We investigate the shuffle-exchange problem in this paper: given a permutation $\pi$ on $[n] \times [m]$ and two permutation groups $G$ on $[n]$ and $H$ on $[m]$, the goal is to generate $\pi$ by alternately using the following two types of operations:

• Select $g_1, g_2, \dotsc , g_m \in G$ and perform each $g_i$ on the $i$-th column of $[n] \times [m]$ in parallel;

• Select $h_1, h_2, \dotsc, h_n \in H$ and perform each $h_j$ on the $j$-th row of $[n] \times [m]$ in parallel.

We discuss the shuffle-exchange, i.e., the composition of these allowable operations, from the perspective of the Cayley graph.

For cases where the base groups G and H are both cyclic groups, we prove that the diameter of the underlying Cayley graph, i.e., the minimum number of steps sufficient to achieve any permutation, is upper bounded by $O (\min {\lbrace n + m, n \log m, m \log n \rbrace})$, which is asymptotically optimal when $\min {\lbrace n, m \rbrace} = O(1)$ or $n = \Theta (m)$. The main idea is to simulate the shuffle-exchange over symmetric groups with cyclic operations and further accelerate the process with the low-depth periodic switching network. For the shuffle-exchange over general groups, we characterize the reachability of any two given vertices on the Cayley graph, and prove the minimum number of steps to achieve a permutation, if possible, is $O(nm)$. This implies that though a connected component of the Cayley graph could contain exponential number of vertices, its diameter is only at most a polynomial of $n, m$.