Josh Ascher
Josh Ascher
Home Institution
University of Pittsburgh
Year Participated
2022
Year in School
Undergraduate
REU Faculty Mentor
Ling Ren
Research Area Interest
Programming Languages, Formal Methods, and Software Engineering
Biography & Research Abstract
Abstract:
A directed acylic graph(DAG) is (e,d)-depth robust if, for any set of vertices S, with the size of S is less than or equal to e, the graph contains a path of length greater than or equal to d. In other words, a DAG is depth robust if removing any set of vertices that is not too large does not substantially decrease the length of the longest path. We already have algorithms for generating such graphs, as well as both upper and lower bounds on the size that a graph must satisfy to be depth robust. However, the sharpness of these bounds is unknown. We test multiple strategies for removing vertices with the best chance of decreasing the length of the longest path and attempt to improve the algorithm by decreasing the size of the graph. This has many applications to memory hard functions which we do not cover but direct the interested reader to.
Bio:
My name is Josh Ascher. I am studying math and computer science at the University of Pittsburgh. Over the last year, I have become very interested in theoretical CS and discrete math. My previous research experience centered on continuous math; in particular, I studied metric spaces and shortest curves in those spaces. After graduating, I plan to attend graduate school to study theoretical CS and/or math.
Outside of academics, I love to be outdoors and to get exercise. When I am at home, I enjoy taking walks with my dog. I also love reading science fiction and baking/cooking.