WORKSHOP

New Horizons in Stringology
De nouveaux horizons en algorithmique du texte

29 July – 2 August, 2024

Organizing Committee
Comité d’organisation

Gabriel Bathie (Université de Bordeaux & ENS Paris)
Paweł Gawrychowski (University of Wrocław)
Garance Gourdel (IRISA Rennes & ENS Paris)
Tatiana Starikovskaya (ENS Paris)

   Stringology is the branch of computer science that deals with the study of strings or sequences of characters. This field focuses on developing algorithms, data structures, and techniques for processing, analyzing, and manipulating string data.
   Stringology encompasses a wide range of applications, including text processing, Bioinformatics, data compression, cryptography, and artificial intelligence. Some common tasks in stringology include searching for specific patterns in strings, finding the longest common substring between two strings, and computing the edit distance between two strings.
   Stringology algorithms and techniques have become increasingly important as the amount of data in the world continues to grow. With the rise of big data and the Internet of Things, string processing has become a critical component of many modern technologies and applications. Another layer of difficulty stems from the fact that in these applications the data is usually noisy, calling for robust processing methods. Many classical algorithms and data structures are designed to work with exact data and those that do allow for errors in the input usually have unfavourable time and space complexities. This brings the need to search for new approaches and techniques that are better suited for such a setting.

Les algorithmes du texte ont traditionnellement été utilisés dans des domaines tels que la bio-informatique, la sécurité numérique (par exemple dans la détection d’intrusion), la recherche d’informations (par exemple dans l’analyse de textes et de musique). Le rythme de croissance toujours plus rapide du volume de données de chaînes disponibles dans ces applications impose un besoin urgent d’algorithmes à grande échelle et ultra-efficaces pour le traitement des textes. La quantité totale de données produites double environ tous les sept mois, ce qui est plus rapide que ce que prévoyait la loi de Moore.
   Une autre difficulté vient du fait que dans ces applications, les données sont généralement bruitées, ce qui nécessite des méthodes de traitement robustes. De nombreux algorithmes et structures de données classiques sont conçus pour traiter des données exactes, et ceux qui autorisent des erreurs dans les données d’entrée ont généralement des contraintes de temps et d’espace défavorables. D’où la nécessité de rechercher de nouvelles approches et techniques qui sont mieux adaptées à ce type d’environnement.
   Ce workshop se concentrera sur les fondements du traitement des données massives et bruyantes, y compris, mais sans s’y limiter, (i) la conception d’algorithmes efficaces dans les modèles de calcul à accès restreint (par exemple, algorithmes de streaming, testeurs de propriété), (ii) la conception de structures de données plus efficaces grâce à l’approximation et à la randomisation, et (iii) l’utilisation de la compression pour traiter la grande quantité de données (soit avec des méthodes classiques sans perte, qui utilisent la répétitivité de l’entrée pour la représenter de manière compacte, ou les méthodes avec perte, telles que des sketches, qui permettent de ne stocker qu’une partie de l’information. Nous nous concentrerons particulièrement sur les applications de ces approches en bio-informatique, où la France est l’un des leaders mondiaux.

SPEAKERS

Antoine Amarilli (Télécom Paris)   Strings in data management: enumeration and incremental maintenance
Gabriel Bathie (Université de Bordeaux)   The complexity of testing regular languages
Ruben Becker (Ca’ Foscari University of Venice)   Wheeler Automata
Giulia Bernardini (University of Trieste)   Utility-oriented string mining
Itai Boneh (University of Haifa)   Optimal Dynamic Time Warping on Run-Length Encoded Strings
Diego Diaz  (University of Helsinki)   Techniques for Editing Grammar-Compressed Text
Bartlomiej Dudek (University of Wroclaw)   Sorting Signed Permutations by Reversals in Nearly-Linear Time
Jonas Ellert (Technical University of Dortmung)   Palindromic Length in Streaming
Travis Gagie (Dalhousie University)   On the design of pangenomic indexes
Pawel Gawrychowski  (University of Wroclaw)   Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration
Daniel Gibney  (University of Texas at Dallas)   k-CSS – Transitions between Longest Common Substring and Longest Common Subsequence
Shay Golan  (University of Haifa)    String 2-Covers with No Length Restrictions
Egor Gorbachev  (Saarland University)   Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
Adam Górkiewicz  (University of Wrocław)    Approximate 2D pattern matching
Samah Idrees-ghazawi (Braude College of Engineering Karmiel)   Optimal Bounds for Distinct Quartics
Shunsuke Inenaga  (Kyushu University)   Computing Minimal Absent Words and Extended Bispecial Factors with CDAWG Space
Ce Jin  (Massachusetts Institute of Technology)   Additive structure in approximate pattern matching problems
Tomasz Kociumaka  (Max Planck Institute for Informatics)   Compressed Text Indexing in δ-Optimal Space
Michal Koucky (Charles University)   Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching
Gregory Kucherov (Université Gustave Eiffel)   Better space-time-robustness trade-offs for set reconciliation
Ray Li  (Santa Clara University)   Binary Longest Common Subsequences
Charles Paperman (Université de Lille)   Streaming, parallelism and vectorization
Nicola Prezza (Ca’ Foscari University of Venice)   Sketching and Streaming for Data Compression
Jakub Radoszewski (University of Warsaw)   Linear Time Construction of Cover Suffix Tree and Applications
Leena Salmela (University of Helsinki)   Analysis of structural correctness of sequence assembly
Teresa Anna Steiner (Technical University of Denmark)   Differential Privacy for Strings
Philip Simon Whittington (ETH Zürich)   Online String Attractors

SPONSOR

Approximation and Randomised String Processing