MPC Reading Group : Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
Date:
This is a paper reading in MPC reading group. This paper focuses on lower bound of MPC computation. In this paper, firstly, the authors defined a new computation model called s-SHUFFLE, which can simulate MapReduce computation. Secondly, the authors proves that s-SHUFFLE computes a function with a polynomial representation of degree $n$ requires $\lceil \log_s n\rceil$ rounds. Thirdly, the authors proves that such lower bound is almost the best result of s-SHUFFLE computation. Furturemore, the authors apply the sophisticated toolbox known for polynomials to reason about these computations. Download slides used in this presentation here