  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 any constant $c > 0$, it is Unique Games hard to approximate
$\mathsf{cc}(G)$ to within a factor of $c$.
  (See the paper for the full abstract.)
