In this work, we study periodicity in strings with wildcards. A string T with at most k wildcards is called strongly (p,k)-periodic if the wildcards in T can be replaced with alphabet symbols to obtain a string with period p, and weakly (p,k)-periodic if T[i] matches T[i+p] for all i. Intuitively, both generalize to (≤ g, k)-periodicity, which is the property of being (p,k)-periodic for some p ∈ [1..g]. An ε-tester for a property 𝒫 is an algorithm that distinguishes between strings that satisfy 𝒫 and strings where one needs to change at least an ε-fraction of the symbols to obtain a string that satisfies 𝒫. We study one-sided error testers, where strings satisfying 𝒫 must always be accepted, while strings that are ε-far must be rejected with probability at least 2/3. The complexity of a tester is the worst-case number of symbols of an input of length n it must read to make the decision. We design the following testers for p,g ≤ n/2: 1) An ε-tester for strong (p,k)-periodicity with complexity Õ_ε(1) . 2) An ε-tester for strong (≤ g,k)-periodicity with complexity Õ_ε(√g). 3) An ε-tester for weak (p,k)-periodicity with complexity Õ_ε(min(k, n /(k+p))). 4) An ε-tester for weak (≤ g,k)-periodicity with complexity Õ_ε(min(k+ √{gk}, n/√k)). Additionally, we show a lower bound on the complexity of ε-testers for weak (≤ g,k)-periodicity, implying that our tester for weak (≤ g,k)-periodicity is optimal up to a multiplicative (ε^{-1} ln(gk))^O(1) factor for a wide range of g and k. Finally, our tester for strong (≤ g,k)-periodicity generalizes the one of [Lachish and Newman; Algorithmica 2011] for strings without wildcards, matching (up to polylogarithmic factors) the unconditional lower bound of ̃Ω(√g) in said work for constant ε.

In approximate circular pattern matching the goal is to compute all approximate occurrences of all rotations of a pattern P in a text T. We study this problem under the two most fundamental string distance metrics, the Hamming distance and the edit distance, in the setting where the text arrives online and the available space is limited. Specifically, we wish to report each ending position j of an approximate occurrence before symbol T[j+1] arrives, using sublinear space on top of having read-only access to P and (the seen prefix of) T. For both variants, we present algorithms that use O(poly(k)) extra space and process each arriving symbol in O(poly(k)) time. Notably, with an overhead, our algorithms can be lifted to the asymmetric streaming setting, where we only have read-only access to the pattern for free and account for all extra space.

Many string processing problems can be phrased in the streaming setting, where the input arrives symbol by symbol and we have sublinear working space. The area of streaming algorithms for string processing has flourished since the seminal work of Porat and Porat [FOCS 2009]. Unfortunately, problems with efficient solutions in the classical setting often do not admit efficient solutions in the streaming setting. As a bridge between these two settings, Saks and Seshadhri [SODA 2013] introduced the asymmetric streaming model (see also [Andoni, Krauthgamer, and Onak; FOCS 2010]). Here, one is given read-only access to a (typically short) reference string R of length m, while a (typically long) text T arrives as a stream. We provide a generic technique to reduce fundamental string problems in the asymmetric streaming model to the online read-only model, lifting several existing algorithms and generally improving upon the state of the art. Most notably, we obtain asymmetric streaming algorithms for exact and approximate pattern matching (under both the Hamming and edit distances), and for relative Lempel-Ziv compression, a popular scheme for measuring and exploiting redundancy in repetitive text collections. At the heart of our approach lies a novel tool that facilitates efficient computation in the asymmetric streaming model: the suffix random access data structure. In its simplest variant, it maintains constant-time random access to the longest suffix of (the seen prefix of) T that occurs in R. Let τ be a parameter that denotes the size of the data structure. A straightforward approach maintains the data structure in {O}(m/τ) time per arriving symbol of T. We drastically improve this tradeoff and reveal fundamental barriers via a bidirectional reduction between suffix random access and function inversion, a central problem in cryptography: - By leveraging Fiat and Naor’s function inversion data structure [SIAM J. Comput. 2000], we achieve Õ(1+m³/τ⁶) update time. In particular, for τ = √m, we obtain Õ(1) update time, improving over the Ω(√m) bound of the straightforward solution. - We establish an unconditional Ω̃(m/τ³) lower bound on the update time. Additionally, we show that achieving update time o(m³/τ⁷) would imply a breakthrough in function inversion. On the way to our upper bound, we propose a variant of the string synchronizing sets ([Kempa and Kociumaka; STOC 2019]) with a local sparsity condition that, as we show, admits an efficient streaming construction algorithm. We believe that our framework and techniques will find broad applications in the development of small-space string algorithms.

In this work, we study the problem of detecting periodic trends in strings. While detecting exact periodicity has been studied extensively, real-world data is often noisy, where small deviations or mismatches occur between repetitions. This work focuses on a generalized approach to period detection that efficiently handles noise. Given a string S of length n, the task is to identify integers p such that the prefix and the suffix of S, each of length n-p+1, are similar under a given distance measure. Ergün et al. [APPROX-RANDOM 2017] were the first to study this problem in the streaming model under the Hamming distance. In this work, we combine, in a non-trivial way, the Hamming distance sketch of Clifford et al. [SODA 2019] and the structural description of the k-mismatch occurrences of a pattern in a text by Charalampopoulos et al. [FOCS 2020] to present a more efficient streaming algorithm for period detection under the Hamming distance. As a corollary, we derive a streaming algorithm for detecting periods of strings which may contain wildcards, a special symbol that match any character of the alphabet. Our algorithm is not only more efficient than that of Ergün et al. [TCS 2020], but it also operates without their assumption that the string must be free of wildcards in its final characters. Additionally, we introduce the first two-pass streaming algorithm for computing periods under the edit distance by leveraging and extending the Bhattacharya-Koucký’s grammar decomposition technique [STOC 2023].

The Metropolis algorithm (MA) is a classic stochastic local search heuristic. It avoids getting stuck in local optima by occasionally accepting inferior solutions. To better and in a rigorous manner understand this ability, we conduct a mathematical runtime analysis of the MA on the CLIFF benchmark. Apart from one local optimum, cliff functions are monotonically increasing towards the global optimum. Consequently, to optimize a cliff function, the MA only once needs to accept an inferior solution. Despite seemingly being an ideal benchmark for the MA to profit from its main working principle, our mathematical runtime analysis shows that this hope does not come true. Even with the optimal temperature (the only parameter of the MA), the MA optimizes most cliff functions less efficiently than simple elitist evolutionary algorithms (EAs), which can only leave the local optimum by generating a superior solution possibly far away. This result suggests that our understanding of why the MA is often very successful in practice is not yet complete. Our work also suggests to equip the MA with global mutation operators, an idea supported by our preliminary experiments.