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

Project Title
Concrete Attacks on Depth Robust Graphs

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.