Approximating Cumulative Pebbling Cost is Unique Games Hard

Jeremiah Blocki, Seunghoon Lee, Samson Zhou

The cumulative pebbling complexity of a directed acyclic graph $G$ is defined as $\mathsf{cc}(G)={\min }_P{\sum }_i|P_i|$, where the minimum is taken over all legal (parallel) black…