The construction and application of depth-robust graphs
Lee, Jong Chan
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.