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 pebblings of \(G\) and \(|P_i|\) denotes the number of pebbles on the graph during round \(i\). Intuitively, \(\mathsf{cc}(G)\) captures the amortized Space-Time complexity of pebbling \(m\) copies of \(G\) in parallel. The cumulative pebbling complexity of a graph \(G\) is of particular interest in the field of cryptography as \(\mathsf{cc}(G)\) is tightly related to the amortized Area-Time complexity of the Data-Independent Memory-Hard Function (iMHF) \(f_{G,H}\) [AS15] defined using a constant indegree directed acyclic graph (DAG) \(G\) and a random oracle \(H(\cdot)\). A secure iMHF should have amortized Space-Time complexity as high as possible, e.g., to deter brute-force password attacker who wants to find \(x\) such that \(f_{G,H}(x) = h\). Thus, to analyze the (in)security of a candidate iMHF \(f_{G,H}\), it is crucial to estimate the value \(\mathsf{cc}(G)\) but currently, upper and lower bounds for leading iMHF candidates differ by several orders of magnitude. Blocki and Zhou recently showed that it is \(\mathsf{NP}\)-Hard to compute \(\mathsf{cc}(G)\), but their techniques do not even rule out an efficient \((1+\varepsilon)\)-approximation algorithm for any constant \(\varepsilon>0\). We show that for \(\mathit{any}\,\) constant \(c > 1\), it is Unique Games hard to approximate \(\mathsf{cc}(G)\) to within a factor of \(c\).
Along the way, we show the hardness of approximation of the DAG Vertex Deletion problem on DAGs of constant indegree. Namely, we show that for any \(k,\varepsilon >0\) and given a DAG \(G\) with \(N\) nodes and constant indegree, it is Unique Games hard to distinguish between the case that \(G\) is \((e_1, d_1)\)-reducible with \(e_1=N^{1/(1+2\varepsilon)}/k\) and \(d_1=k N^{2\varepsilon/(1+2\varepsilon)}\), and the case that \(G\) is \((e_2, d_2)\)-depth-robust with \(e_2 = (1-\varepsilon)k e_1\) and \(d_2= 0.9 N^{(1+\varepsilon)/(1+2\varepsilon)}\), which may be of independent interest. Our result generalizes a result of Svensson who proved an analogous result for DAGs with indegree \(\mathcal{O}(N)\).