Reconstructing the evolutionary history of tumors using single-cell sequencing (SCS) data presents significant computational challenges. Existing approaches are either computationally intractable for emerging large-scale datasets or rely on heuristics that lack optimality guarantees. In this work, we propose a novel, time-efficient algorithm that constructs the phylogenetic tree of tumor evolution with a provable guarantee of optimality. Our main result is a branch-and-bound algorithm that reconstructs the most likely tumor evolutionary history up to two orders of magnitude faster than the previous best algorithm. To achieve this, we use efficient and well-known 2-approximation algorithms for the Vertex Cover problem to prune the branch-and-bound tree effectively. Unlike previous works' polynomial-time branch-and-bound bounding strategies, our bounding algorithm provides strong worst-case theoretical guarantees, leading to faster reconstruction of the tumor evolution.

In this paper, we present the first dynamic algorithms for Dyck edit distance and tree edit distance that achieve subpolynomial update times. Dyck edit distance measures how far a parenthesis string is from a wellparenthesized expression (i.e., the Dyck language), while tree edit distance quantifies the minimum number of node insertions, deletions, and substitutions required to transform one rooted, ordered, and labeled tree into another. These problems have been studied extensively since the 1970s, with recent advances in both algorithmic efficiency and fine-grained complexity lower bounds. Despite this progress, no prior work has addressed efficient dynamic algorithms for these problems, even though many real-world applications involve evolving structured data such as LaTeX, JSON, XML, HTML, hierarchical datasets, and RNA secondary structures. We take the first step in this direction by designing new approximation algorithms for Dyck and tree edit distances in the dynamic setting. Our key technical contribution is a set of novel reduction and decomposition techniques that transform instances of Dyck and tree edit distance into efficiently maintainable instances of string edit distance. Leveraging existing dynamic algorithms for string edit distance, we obtain an $n^{o(1)}$ approximation for Dyck edit distance with $n^{o(1)}$ update time. This builds upon and significantly extends prior work on Dyck language decomposition ([Saha, FOCS’14] and [Koucký & Saks; SODA’23]). For tree edit distance, we introduce a new static reduction that improves the best-known approximation bound from $O\left(n^{3 / 4}\right)$ [Akutsu, Fukagawa, and Takasu; Algorithmica, 2010] to $\tilde{O}(\sqrt{n})$. Moreover, while the previous result was restricted to constant-degree trees, ours holds for arbitrary trees. We then extend our reduction dynamically, yielding a dynamic tree edit distance algorithm with an approximation factor of $n^{1 / 2+o(1)}$ and update time $n^{o(1)}$. A core component of our approach is a new dynamic maintenance algorithm for heavy-light decomposition, a widely used technique in tree algorithms. Given its broad applicability, we believe this result is of independent interest. Finally, we introduce a novel static and dynamic decomposition method that achieves an $\tilde{O}(k)$-approximation for tree edit distance when the tree edit distance is at most k; combined with the trivial bound $k \leq n$, this yields a deterministic $\tilde{O}(\sqrt{n})$-approximation. While similar decompositions exist for strings, no prior work has successfully extended them to trees. Our approach breaks this barrier, improving the best-known approximations for tree edit distance both in the static and dynamic setting. In the static setting, our algorithm runs in $\tilde{O}(n)$ time; in the dynamic setting, it only requires a polylogarithmic worst-case update time. The state-of-the-art near-lineartime static algorithm for tree edit distance previously achieved an $O(\sqrt{n})$-approximation [Boroujeni, Ghodsi, Hajiaghayi, and Seddighin; STOC’19].

In the Massively Parallel Computation (MPC) model, data is distributed across multiple processors, and we call an algorithm space-efficient if each machine has n^1-ε + o(1) memory with a machine count of Ømega(n^ε).

Regular languages are some of the most widely studied languages in computer science history. Given a regular language L ⊆ {0, 1} ⋆ and string ω ∈ {0, 1} ⋆, two of the most fundamental regular language problems are recognition, the problem of determining if w is in L, and testing, the problem of determining if w is at most ε-far from L. In this paper we modernize regular language recognition and testing algorithms for the Massively Parallel Computations (MPC) model used everyday in big data engineering. First we give a regular language testing algorithm, which succeeds with high probability using Õ(1 over ε) queries to the input string. Following the testing algorithm, we give a simple dynamic programming solution for regular language recognition. Both algorithms run in constant communication rounds and O(n) total memory in MPC where n is the size of the input.

A suffix tree is a trie-like data structure that stores every suffix of an input string of length n. Finding the Suffix Tree of a given string is a well-studied and classic problem. A compressed suffix tree is constructible in O(n) time using the well-known algorithm of McCreight (JACM, 1976). Suffix trees alongside with hashing are two powerful tools in solving location-sensitive string problems. Many well-studied fundamental string problems such as String Matching, Longest Palindrome Substring (LPS), Longest Common Substring (LCS), and Longest Common Prefix (LCP) queries are location-sensitive and have linear time solutions via reductions to suffix tree.

Given two strings of length n over alphabet Σ, and an upper bound k on their edit distance, the algorithm of Myers (Algorithmica’86) and Landau and Vishkin (JCSS’88) from almost forty years back computes the unweighted string edit distance in O(n+k2) time. To date, it remains the fastest algorithm for exact edit distance computation, and it is optimal under the Strong Exponential Hypothesis (Backurs and Indyk; STOC’15). Over the years, this result has inspired many developments, including fast approximation algorithms for string edit distance as well as similar Õ(n+poly(k))-time algorithms for generalizations to tree and Dyck edit distances. Surprisingly, all these results hold only for unweighted instances.

In this paper, we generalize the recently studied stochastic matching problem to more accurately model a significant medical process, kidney exchange, and several other applications. Up until now the stochastic matching problem that has been studied was as follows: given a graph G= (V,E), each edge is included in the realized sub-graph of G independently with probability pe, and the goal is to find a degree-bounded sub-graph Q of G that has an expected maximum matching that approximates the expected maximum matching of G. This model does not account for possibilities of vertex dropouts, which can be found in several applications, e.g. in kidney exchange when donors or patients opt out of the exchange process as well as in online freelancing and online dating when online profiles are found to be faked. Thus, we will study a more generalized model of stochastic matching in which vertices and edges are both realized independently with some probabilities pv, pe, respectively, which more accurately fits important applications than the previously studied model. We will discuss the first algorithms and analysis for this generalization of the stochastic matching model and prove that they achieve good approximation ratios. In particular, we show that the approximation factor of a natural algorithm for this problem is at least 0.6568 in unweighted graphs, and 1/2+ε in weighted graphs for some constant ε >0. We further improve our result for unweighted graphs to 2/3 using edge degree constrained sub-graphs (EDCS).

Computing the edit distance of two strings is one of the most basic problems in computer science and combinatorial optimization. Tree edit distance is a natural generalization of edit distance in which the task is to compute a measure of dissimilarity between two (unweighted) rooted trees with node labels. Perhaps the most notable recent application of tree edit distance is in NoSQL big databases, such as MongoDB, where each row of the database is a JSON document represented as a labeled rooted tree and finding dissimilarity between two rows is a basic operation. Until recently, the fastest algorithm for tree edit distance ran in cubic time (Demaine, Mozes, Rossman, Weimann; TALG’10); however, Mao (FOCS’21) broke the cubic barrier for the tree edit distance problem using fast matrix multiplication.Given a parameter k as an upper bound on the distance, an $\mathcal{O}(n+k^{2})$-time algorithm for edit distance has been known since the 1980s due to works of Myers (Algorithmica’86) and Landau and Vishkin (JCSS’88). The existence of an $\tilde{\mathcal{O}}(n+poly(k))$-time algorithm for tree edit distance has been posed as open question, e.g., by Akmal and Jin (ICALP’21), who give a stateof-the-art $O(nk^{2})$-time algorithm. In this paper, we answer this question positively.