We study the space complexity of pattern matching in the asymmetric streaming model, focusing on approximate pattern matching under the Hamming and edit distances. In this problem, we are given an m-length pattern and an n-length text and must compute, for every position of the text, the smallest distance between the pattern and a substring of the text which ends at this position. In the asymmetric streaming model, we assume to have constant-time random access to the pattern, while the text arrives as a stream, one letter at a time. It is known that computing all distances exactly in the asymmetric streaming model requires Ω(m) space (for the edit distance see Li and Zheng [FSTTCS 2021]). Hence, to achieve sublinear space, a relaxation of the problem is necessary. One possible variant is to consider the small distance regime, where the algorithm must compute only those distances that are bounded by a small integer parameter k. In this case, existing algorithms in a more restrictive fully streaming model (Kociumaka, Clifford, Porat [SODA'19], Bhattacharya, Koucký [ICALP'23]) straightforwardly imply the existence of poly(k, log n)-space asymmetric streaming algorithms. Another possible relaxation is computing all distances approximately. For this variant, we don't have small-space algorithms in the fully streaming model: the best known algorithm solves pattern matching under the Hamming distance (1+ε)-approximately using 𝒪̃(ε^{-2}√m) space (Starikovskaya, Svagerka, Uznański [APPROX'20]). For the edit distance, no efficient approximation algorithms are known. In this work, we show approximation algorithms for pattern matching under the Hamming and edit distances in the asymmetric streaming model for any constant ε > 0: 1) We show that there is a simple randomised asymmetric streaming algorithm that solves approximate pattern matching under the Hamming distance (1+ε)-approximately using 𝒪(ε^{-3}log³n) bits. 2) As our second and main contribution, we extend the result of Cheng et al. [ICALP 2021] and show that for any integer k there is a deterministic asymmetric streaming algorithm that solves pattern matching under the edit distance (2^k-1+ε)-approximately using 𝒪̃(m^{1/k}) space.

A permutation graph is the intersection graph of a set of segments between two parallel lines. In other words, they are defined by a permutation $π$ on $n$ elements, such that $u$ and $v$ are adjacent if an only if $uπ(v)$. We consider the problem of computing the distances in such a graph in the setting of informative labeling schemes. The goal of such a scheme is to assign a short bitstring $\ell(u)$ to every vertex $u$, such that the distance between $u$ and $v$ can be computed using only $\ell(u)$ and $\ell(v)$, and no further knowledge about the whole graph (other than that it is a permutation graph). This elegantly captures the intuition that we would like our data structure to be distributed, and often leads to interesting combinatorial challenges while trying to obtain lower and upper bounds that match up to the lower-order terms. For distance labeling of permutation graphs on $n$ vertices, Katz, Katz, and Peleg [STACS 2000] showed how to construct labels consisting of $\mathcal{O}(\log^{2} n)$ bits. Later, Bazzaro and Gavoille [Discret. Math. 309(11)] obtained an asymptotically optimal bounds by showing how to construct labels consisting of $9\log{n}+\mathcal{O}(1)$ bits, and proving that $3\log{n}-\mathcal{O}(\log{\log{n}})$ bits are necessary. This however leaves a quite large gap between the known lower and upper bounds. We close this gap by showing how to construct labels consisting of $3\log{n}+\mathcal{O}(\log\log n)$ bits.

A routing labeling scheme assigns a binary string, called a label, to each node in a network, and chooses a distinct port number from {1, …, d} for every edge outgoing from a node of degree d. Then, given the labels of u and w and no other information about the network, it should be possible to determine the port number corresponding to the first edge on the shortest path from u to w. In their seminal paper, Thorup and Zwick [SPAA 2001] designed several routing methods for general weighted networks. An important technical ingredient in their paper that according to the authors “may be of independent practical and theoretical interest” is a routing labeling scheme for trees of arbitrary degrees. For a tree on n nodes, their scheme constructs labels consisting of (1 + o(1)) log n bits such that the sought port number can be computed in constant time. Looking closer at their construction, the labels consist of bits. Given that the only known lower bound is log n + Ω(log log n), a natural question that has been asked for other labeling problems in trees is to determine the asymptotics of the smaller-order term. We make the first (and significant) progress in 19 years on determining the correct second-order term for the length of a label in a routing labeling scheme for trees on n nodes. We design such a scheme with labels of length .

We revisit the problem of maintaining the longest increasing subsequence (LIS) of an array under (i) inserting an element, and (ii) deleting an element of an array. In a recent breakthrough, Mitzenmacher and Seddighin [STOC 2020] designed an algorithm that maintains an O((1/є)O(1/є))-approximation of LIS under both operations with worst-case update time Õ(nє), for any constant є>0 (Õ hides factors polynomial in logn, where n is the length of the input). We exponentially improve on their result by designing an algorithm that maintains an (1+є) approximation of LIS under both operations with worst-case update time Õ(є−5). Instead of working with the grid packing technique introduced by Mitzenmacher and Seddighin, we take a different approach building on a new tool that might be of independent interest: LIS sparsification.