On Explicit Constructions of Extremely Depth Robust Graphs
| Autor: | Blocki, Jeremiah, Cinkoske, Mike, Lee, Seunghoon, Son, Jin Young |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Mathematics of computing ��� Graph theory
FOS: Computer and information sciences Computer Science - Cryptography and Security Explicit Constructions Proofs of Space and Replication Mathematics of computing ��� Paths and connectivity problems Theory of computation ��� Cryptographic primitives Mathematics of computing ��� Combinatorics Computer Science - Data Structures and Algorithms FOS: Mathematics Data-Independent Memory Hard Functions Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) Combinatorics (math.CO) Cryptography and Security (cs.CR) Depth-Robust Graphs MathematicsofComputing_DISCRETEMATHEMATICS |
| DOI: | 10.48550/arxiv.2110.04190 |
| Popis: | A directed acyclic graph $G=(V,E)$ is said to be $(e,d)$-depth robust if for every subset $S \subseteq V$ of $|S| \leq e$ nodes the graph $G-S$ still contains a directed path of length $d$. If the graph is $(e,d)$-depth-robust for any $e,d$ such that $e+d \leq (1-\epsilon)|V|$ then the graph is said to be $\epsilon$-extreme depth-robust. In the field of cryptography, (extremely) depth-robust graphs with low indegree have found numerous applications including the design of side-channel resistant Memory-Hard Functions, Proofs of Space and Replication, and in the design of Computationally Relaxed Locally Correctable Codes. In these applications, it is desirable to ensure the graphs are locally navigable, i.e., there is an efficient algorithm $\mathsf{GetParents}$ running in time $\mathrm{polylog} |V|$ which takes as input a node $v \in V$ and returns the set of $v$'s parents. We give the first explicit construction of locally navigable $\epsilon$-extreme depth-robust graphs with indegree $O(\log |V|)$. Previous constructions of $\epsilon$-extreme depth-robust graphs either had indegree $\tilde{\omega}(\log^2 |V|)$ or were not explicit. Comment: 12 pages, 1 figure. This is the full version of the paper published at STACS 2022. We noticed a mistake in the references for the computational intractability of the depth robustness of the graphs and fixed it |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|