## ITCS 2020: Approximating Cumulative Pebbling Cost is Unique Games Hard

### Abstract.

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)$$.

### Further Materials.

• Full Paper: [Link]
• Slides for the 3-Minute Summary: [Link]
• Slides for the Full Presentation: [Link]