Fundamental computer science problems such as edit distance have been well-studied for decades, and algorithms for these problems have become established and widespread. In modern times, however, achieving even faster algorithms for more specific scenarios finds increasing value as dataset sizes become larger and computer application settings become more varied. While a polynomial-time solution in the static sequential setting may be known and straightforward to implement, it may not quick in an online setting or take advantage of structural properties inherent to the problem setting that could lead to a more efficient solution. Parameterized algorithms and algorithms specifically designed for parallel or dynamic settings help address these gaps in algorithm utility and understanding, bringing a fresh lens to old problems.
In this work, we start by studying algorithms for string, tree, and Dyck edit distance with runtimes parameterized by the distance itself, termed the "bounded-distance" regime. We begin by giving an O(n + poly(k))-time algorithm for tree edit distance, answering a longstanding open question on the existence of such an algorithm (where k represents the distance). Expanding on our tree edit distance approach, we then give the first O(n + poly(k))-time algorithms for weighted string, weighted tree, and weighted Dyck edit distance.
Beyond the bounded-distance regime, we give dynamic solutions for tree and Dyck edit distance. For each, we provide novel dynamic reductions to string edit distance matching state-of-the-art approximation factors from the static setting. To do so, we utilize a novel dynamic heavy-light decomposition implementation of our own complemented by a dynamic strings data structure from the literature.
Finally, we consider edit distance and related string problems in the Massively Parallel Computations (MPC) model. We give an approximation algorithm for edit distance in subpolynomial rounds with subpolynomial approximation factor, and conjecture on the hardness of the problem in MPC. We then end with constant-round MPC algorithms for longest palindrome, longest common substring, and suffix tree construction.
Jacob Gilbert is a PhD student at University of Maryland studying string and graph algorithms under Dr. MohammadTaghi Hajiaghayi. Jacob has recently been interested in the classic edit distance problem and its tree and Dyck variants in several settings, such as the Massively Parallel Computations and dynamic settings. These problems see applications ranging from fundamental database operations to comparing cell phylogenies. By leveraging new algorithmic tools for strings and investigating the inherent structure within these problems, Jacob has worked to help provide novel approaches to these problems beyond the standard sequential and static theoretical setting. He has several publications in high tier conferences such as STOC and FOCS.