License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.64
URN: urn:nbn:de:0030-drops-136038
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13603/
Blocki, Jeremiah ;
Cinkoske, Mike
A New Connection Between Node and Edge Depth Robust Graphs
Abstract
Given a directed acyclic graph (DAG) G = (V,E), we say that G is (e,d)-depth-robust (resp. (e,d)-edge-depth-robust) if for any set S ⊂ V (resp. S ⊆ E) of at most |S| ≤ e nodes (resp. edges) the graph G-S contains a directed path of length d. While edge-depth-robust graphs are potentially easier to construct many applications in cryptography require node depth-robust graphs with small indegree. We create a graph reduction that transforms an (e, d)-edge-depth-robust graph with m edges into a (e/2,d)-depth-robust graph with O(m) nodes and constant indegree. One immediate consequence of this result is the first construction of a provably ((n log log n)/log n, n/{(log n)^{1 + log log n}})-depth-robust graph with constant indegree, where previous constructions for e = (n log log n)/log n had d = O(n^{1-ε}). Our reduction crucially relies on ST-Robust graphs, a new graph property we introduce which may be of independent interest. We say that a directed, acyclic graph with n inputs and n outputs is (k₁, k₂)-ST-Robust if we can remove any k₁ nodes and there exists a subgraph containing at least k₂ inputs and k₂ outputs such that each of the k₂ inputs is connected to all of the k₂ outputs. If the graph if (k₁,n-k₁)-ST-Robust for all k₁ ≤ n we say that the graph is maximally ST-robust. We show how to construct maximally ST-robust graphs with constant indegree and O(n) nodes. Given a family ? of ST-robust graphs and an arbitrary (e, d)-edge-depth-robust graph G we construct a new constant-indegree graph Reduce(G, ?) by replacing each node in G with an ST-robust graph from ?. We also show that ST-robust graphs can be used to construct (tight) proofs-of-space and (asymptotically) improved wide-block labeling functions.
BibTeX - Entry
@InProceedings{blocki_et_al:LIPIcs.ITCS.2021.64,
author = {Jeremiah Blocki and Mike Cinkoske},
title = {{A New Connection Between Node and Edge Depth Robust Graphs}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {64:1--64:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-177-1},
ISSN = {1868-8969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13603},
URN = {urn:nbn:de:0030-drops-136038},
doi = {10.4230/LIPIcs.ITCS.2021.64},
annote = {Keywords: Depth robust graphs, memory hard functions}
}
|
Keywords: |
|
Depth robust graphs, memory hard functions |
|
Collection: |
|
12th Innovations in Theoretical Computer Science Conference (ITCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
04.02.2021 |
