1 Search Results for "Son, Jin Young"

Document
DOI: 10.4230/LIPIcs.STACS.2022.14
On Explicit Constructions of Extremely Depth Robust Graphs

Authors: Jeremiah Blocki, Mike Cinkoske, Seunghoon Lee, and Jin Young Son

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
A directed acyclic graph G = (V,E) is said to be (e,d)-depth robust if for every subset S ⊆ V of |S| ≤ 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 ≤ (1-ε)|V| then the graph is said to be ε-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 GetParents running in time polylog|V| which takes as input a node v ∈ V and returns the set of v’s parents. We give the first explicit construction of locally navigable ε-extreme depth-robust graphs with indegree O(log |V|). Previous constructions of ε-extreme depth-robust graphs either had indegree ω̃(log² |V|) or were not explicit.
Cite as

Jeremiah Blocki, Mike Cinkoske, Seunghoon Lee, and Jin Young Son. On Explicit Constructions of Extremely Depth Robust Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 14:1-14:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{blocki_et_al:LIPIcs.STACS.2022.14,
  author =	{Blocki, Jeremiah and Cinkoske, Mike and Lee, Seunghoon and Son, Jin Young},
  title =	{{On Explicit Constructions of Extremely Depth Robust Graphs}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{14:1--14:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.14},
  URN =		{urn:nbn:de:0030-drops-158241},
  doi =		{10.4230/LIPIcs.STACS.2022.14},
  annote =	{Keywords: Depth-Robust Graphs, Explicit Constructions, Data-Independent Memory Hard Functions, Proofs of Space and Replication}
}
  • Refine by Author
  • 1 Blocki, Jeremiah
  • 1 Cinkoske, Mike
  • 1 Lee, Seunghoon
  • 1 Son, Jin Young

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Paths and connectivity problems
  • 1 Theory of computation → Cryptographic primitives

  • Refine by Keyword
  • 1 Data-Independent Memory Hard Functions
  • 1 Depth-Robust Graphs
  • 1 Explicit Constructions
  • 1 Proofs of Space and Replication

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact