Jeudi 15 janvier 2026, 14:00 à 15:00

salle de séminaire du département d'informatique

Jonas Ellert

(ENS, Paris)

Pattern matching is a fundamental problem in string algorithms; given a short pattern string (e.g., the DNA sequence of a single gene), the task is to locate occurrences of the pattern in a longer text string (e.g., the whole-genome DNA sequence of an individual). In approximate pattern matching, one has to find areas of the text that are similar to the pattern, for some notion of similarity. This problem is well understood for one-dimensional strings when the Hamming distance is used as a similarity measure. However, solutions in more complicated settings—e.g., in advanced models of computation, on multidimensional strings, or using more complex similarity measures—are still emerging. This talk focuses on two such results: two-dimensional pattern matching under Hamming distance, and one-dimensional pattern matching under Cartesian tree Hamming distance. A unifying feature of these and previous results is periodicity; we present notions of two-dimensional periodicity and one-dimensional Cartesian tree periodicity, which are the foundation of the new algorithms.