C1: Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)

February 18, 2025

• Definitions.
• Reference

This post will show how to use algebraic complexity theory to show a lower bound for distributed models.

Definitions.

We first introduce $\perp$-sum. Given $x_1, x_2, \ldots, x_m \in \{0,1,\perp\}$, the $\perp$-sum of $x_1,\ldots,x_m$ is

• 1 if there is exact one in $x_i$.
• 0 if there is exact zero in $x_i$.
• $\perp$ if every $x_i$ is $\perp$.

The input is a string and output is 1 bit.

Now, we define $s$-Shuffle Computation.

1. Consider a $R$-round computation. The input is $x_1,\ldots, x_n$ and the output is $y_1, \ldots, y_k$. Each machine has $s$ ports.
2. Let each $x_i$ assign to a machine and let each $y_i$ assign to a machine.
3. We give each machine a round. Machines corresponding to the input bits have round 0. Machines corresponding to the output bits have round $R+1$. All other machines have rounds in $\{1,\ldots, R\}$.
4. For each pair $(u,v)$ of machines with (round-number) $r(u) < r(v)$, we have a function $\alpha_{u,v}$ transforming $\{0,1,\perp\}^s$ to $\{0,1,\perp\}^s$.

The result of $s$-shuffle computation is as follows.

• For round-0 machine $v$ corresponding to an input $x_i$, the value $g(v)$ is $(x_i, \perp, \ldots, \perp)$.
• Then, the other results are defined recursively. Given the value $g(u)$ for every machine with $r(u) < r(v)$, the value for $v$ is the $\perp$-sum over all previous machines: $g(v) = \circ_{u:r(u) <r(v)} a_{uv}(g(u))$

where $\circ_{i=1}^m \vec{x} = \{\underbrace{i, j,\ldots}_m\}$ $(i,j\in \{0,1, \perp\})$.

Reference

[1]. Roughgarden, T., Vassilvitskii, S. and Wang, J.R., 2018. Shuffles and circuits (on lower bounds for modern parallel computation). Journal of the ACM (JACM), 65(6), pp.1-24.