University of Illinois Urbana-Champaign

The construction and application of depth-robust graphs

Lee, Jong Chan

Content Files
LEE-THESIS-2022.pdf

Permalink

https://hdl.handle.net/2142/116083

Description

Title
The construction and application of depth-robust graphs
Author(s)
Lee, Jong Chan
Issue Date
2022-07-15
Director of Research (if dissertation) or Advisor (if thesis)
Ren, Ling
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(s)
  • depth-robust graphs
  • depth-robustness
Abstract
The concept of depth-robustness was first introduced in 1975 by Erdos, Graham, and Szemeredi [1]. A graph is depth-robust if there exists a long path in the graph even when some number of vertices, as well as all their incident edges, are removed from the graph. Erdos, Graham, and Szemeredi [1] and Valiant [2] prove lower bounds on the number of edges in a depth-robust graph with a given number of vertices. The first construction of provably depth-robust graphs, due to Erdos, Graham, and Szemeredi [1], has a number of edges that is of the same asymptotic order as these lower bounds, proving that the aforementioned lower bounds to be asymptotically tight. This also implies that asymptotically, the construction of Erdos, Graham, and Szemeredi [1] is optimally sparse for a graph that is as depth-robust. There exists, however, a large constant factor gap between the number of edges required by the lower bounds and the number of edges contained in a graph constructed via the method of Erdos, Graham, and Szemeredi [1]. More recently, depth-robust graphs have been discovered to have practical use in the construction of memory-hard functions and proofs of space, which in turn are used in real-world applications such as cryptocurrencies. For efficiency reasons, practical applications prefer depth-robust graphs as sparse, i.e. containing as few edges, as possible. This motivates the search for constructions of depth-robust graphs that are not only asymptotically optimally sparse, but have a number of edges concretely as close as possible to the lower bounds–all the way down to the constant factors. This work proposes the concept of an everywhere expander, a graph that satisfies some property that is a variation/generalization of the properties satisfied by existing depth-robust graph constructions. We prove that an everywhere expander is depth-robust, and thereby reduce the problem of sparse depth-robust graph construction to that of sparse everywhere expander construction. We also present a graph construction algorithm that outputs an everywhere expander with high probability. For graphs with the same provable depth-robustness, those constructed by the new algorithm have fewer than one sixth the number of edges of the construction of Alwen, Blocki, and Harsha [3], and fewer edges by over two orders of magnitude than the construction of Erdos, Graham, and Szemeredi [1]. We use the lower bound of Valiant [2] as a standard to compare the number of edges each depth-robust graph construction against. The number of edges of our proposed everywhere expander construction can be as few as 139 times that required by Valiant’s bound.
Graduation Semester
2022-08
Type of Resource
Thesis
Handle URL
https://hdl.handle.net/2142/116083
Copyright and License Information
Copyright 2022 Jong Chan Lee

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois