The construction and application of depth-robust graphs

Lee, Jong Chan

Permalink

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

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

Copyright and License Information

Copyright 2022 Jong Chan Lee

Owning Collections