High Parallel Complexity Graphs and Memory-Hard Functions

Abstract. Motivated by growing importance of parallelism in modern computational systems, we introduce a very natural generalization to a parallel setting of the powerful (sequential) black pebbling game over DAGs. For this new variant, when considering pebbling graphs with with multiple disconnected components (say when mod-elling the computation of multiple functions in parallel), we demonstrate a significant shortcoming of the two most common types of complexity measures for DAGs inherited from the sequential setting (namely S-complexity and ST-complexity). Thus, to ensure the applicability of the new pebbling game as a tool for proving results about say the amortized hardness of functions being repeatedly evaluated, we introduce a new complexity measure for DAGs called cumulative complexity (CC) and show how it overcomes this problem. With the aim of facilitating the new complexity lower-bounds in parallel settings we turn to the task of finding high CC graphs for the parallel pebbling game. First we look at several types of graphs such as certain stacks of super-concentrators, permutation graphs, bit-reversal graphs and pyramid graphs, which are known to have high (even optimally so) complexity in the sequential setting. We show that all of them have much lower parallel CC then one could hope for from a graph of equal size. This motivates our first main technical result, namely the construction of a new family of constant in-degree graphs whose parallel CC approaches maximality to within a polylogarithmic factor