Reminder: This post contains 1466 words
· 5 min read
· by Xianbin
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.
- 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.
- Let each \(x_i\) assign to a machine and let each \(y_i\) assign to a machine.
- 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\}\).
- 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.