On Explicit Depth Robust Graphs

We study the problem defined by Erd˝os and Szemer�edi in 1975 of constructing sparse depthrobust graphs. Recall that a directed acyclic graph G is (e, d)-depth-robust if it is guaranteed to contain a path of length d even after the deletion of any e nodes and all of their incident edges. The original construction (of nearly optimal depth-robust graphs) of Erd˝os and Szemer�edi required logarithmic in-degree and subsequent work by Mahmoody, Moran, and Vadhan made that construction explicit. One of the major open questions left since that 1975 seminal work was to construct depth-robust graphs of constant degree. Our contribution is the first explicit construction of constant-degree depth-robust graphs. Our construction too enjoys nearly optimal depth-robustness. We accomplish this via a novel expanding graph product operator X that takes three input graphs (G, H, X) with special properties and outputs a new graph. Informally, we show that our operator provides the following guarantee: if G and H are depth-robust graphs and H is a constant-degree expanding graph [RVW00], then G ∗ = X(G, H, X) is a depth-robust graph of size |G| � |H| whose degree depends only additively on degrees of H and X. We then show that the recursive application of the expanding graph product operator yields a simple and explicit iterative construction for constant-degree depth-robust graphs of arbitrary size. In particular, we show that a graph of size n will enjoy (Ω(n ^(1−epsilon) ), Ω(n ^(1−epsilon) ))-depth-robustness for any epsilon > 0 and give an algorithm for computing labels of all nodes that have a direct edge to/from a given node labeled i in time poly(log i). Ours is the first explicitly constructed constant-degree depth robust graph with guaranteed lower bounds on its depth-robustness (in contrast to only probabilistic ii guarantees). Previous explicit constructions were of logarithmic degree or worked only with probability < 1. Beyond theoretical relevance, our construction has practical implications including a new data-independent memory-hard function (iMHF), a desirable cryptographic primitive for crypto-currencies, with guaranteed lower bounds on its memory complexity