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)depthrobust (resp. (e,d)edgedepthrobust) if for any set S ⊂ V (resp. S ⊆ E) of at most S ≤ e nodes (resp. edges) the graph GS contains a directed path of length d. While edgedepthrobust graphs are potentially easier to construct many applications in cryptography require node depthrobust graphs with small indegree. We create a graph reduction that transforms an (e, d)edgedepthrobust graph with m edges into a (e/2,d)depthrobust 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}})depthrobust 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 STRobust 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₂)STRobust 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₁,nk₁)STRobust for all k₁ ≤ n we say that the graph is maximally STrobust. We show how to construct maximally STrobust graphs with constant indegree and O(n) nodes. Given a family 𝕄 of STrobust graphs and an arbitrary (e, d)edgedepthrobust graph G we construct a new constantindegree graph Reduce(G, 𝕄) by replacing each node in G with an STrobust graph from 𝕄. We also show that STrobust graphs can be used to construct (tight) proofsofspace and (asymptotically) improved wideblock 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:164:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771771},
ISSN = {18688969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13603},
URN = {urn:nbn:de:0030drops136038},
doi = {10.4230/LIPIcs.ITCS.2021.64},
annote = {Keywords: Depth robust graphs, memory hard functions}
}
04.02.2021
Keywords: 

Depth robust graphs, memory hard functions 
Seminar: 

12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Issue date: 

2021 
Date of publication: 

04.02.2021 