Click here for the current academic year.
The Monday meetings of the String Algorithms Group of the University of Verona take place every Monday at 5 p.m. (Italian time), and have been taking place online (zoom) since March 2020. We have decided to stick to the online mode (zoom), since several of our regular members are physically in other places (in other cities, in other countries, or even on other continents!)
Working language is English. If you are interested in participating, send me an email.
The person in charge of coordinating the meetings is Simone Lucà (simone dot luca at univr dot it).
List of talks of previous years:
| date | speaker | title | literature |
|---|---|---|---|
| Mon, Mar. 17, 2025 | Zsuzsanna Lipták | A survey of the Bijective BWT | This is joint work with Hideo Bannai and Dominik Köppl. |
| Mon, Mar. 24, 2025 | Davide Cenzato | Using the Suffixient Array to compress the Suffix Array and beyond | Davide Cenzato, Lore Depuydt, Travis Gagie, Sung-Hwan Kim, Giovanni Manzini, Francisco Olivares and Nicola Prezza: Suffixient Arrays: a New Efficient Suffix Array Compression Technique. Paper on arxiv. |
| Mon, Mar. 31, 2025 | Sung-Hwan Kim | Binary Search Tree and Order-isomorphic Matching | |
| Mon, April 7, 2024 | -- | -- | -- |
| Mon, April 14, 2025 | Daniel Puttini | Optimal prefix-suffix queries with applications by Solon Pissis (SOSA 2024) | Solon P. Pissis: Optimal prefix-suffix queries with applications. SOSA 2024. Paper |
| Mon, April 21, 2025 | -- | (Easter Monday) | -- |
| Mon, Apr. 28, 2024 | Simon Puglisi | (cancelled) | |
| Mon, May 5, 2025 | Ferdinando Cicalese | Beyond worst case analysis and learning augmented algorithms | Talk partially based on M. Mitzenmacher and S. Vassilvitskii: Algorithms with Predictions. Communications of the ACM 2022. Paper |
| Mon, May 12, 2025 | Luca Parmigiani | Scalable multiple whole-genome alignment and locally collinear block construction with SibeliaZ | Ilia Minkin and Paul Medvedev: Scalable multiple whole-genome alignment and locally collinear block construction with SibeliaZ. Nat Commun 11, 6327 (2020). Paper. |
| Mon, May 19, 2025 | Francesco Masillo | Speeding up counting in FM-indexes | Aaron Hong, Marco Oliva, Dominik Köppl, Hideo Bannai, Christina Boucher and Travis Gagie: PFP-FM: an accelerated FM-index. Algorithms Mol. Biol. 19(1): 15 (2024). Paper. |
| Mon, May 26, 2025 | Ruben Becker | Bidirectional Dijkstra's Algorithm is Instance-Optimal | Bernhard Haeupler, Richard Hladík, Václav Rozhoň, Robert E. Tarjan, Jakub Tětek: Bidirectional Dijkstra's Algorithm is Instance-Optimal. SOSA (2025). Paper |
| Mon, June 2, 2025 | -- | (Festa della Repubblica) | |
| Mon, June 9, 2025 | Simone Lucà | The rsync algorithm | Andrew Tridgell, and Paul Mackerras: The rsync algorithm. Technical Report 1996. Paper; and Andrew Tridgell: Efficient algorithms for sorting and synchronization. PhD Thesis 1999 |
| Mon, June 16, 2025 | -- | (CPM and StringMasters in Milan) | |
| Mon, June 23, 2025 | Francesca Ugazio | A brief introduction to Communication Complexity | Arora S, Barak B. Computational Complexity: A Modern Approach. Cambridge University Press, 2009; and Roughgarden T. Communication Complexity (for Algorithm Designers), lecture notes, Stanford 2015 (see here). L. Lovász. Communication complexity: A survey. Technical Report TR-204-89, Computer Science Dept., Princeton University, 1989 (see here). |
| Mon, June 30, 2025 | Elena Biagi | Kaminari: a resource-frugal index for approximate colored k-mer queries | Victor Levallois, Yoshihiro Shibuya, Bertrand Le Gal, Rob Patro, Pierre Peterlongo, and Giulio Ermanno Pibiri: Kaminari: a resource-frugal index for approximate colored k-mer queries. Paper on bioarxiv |
| date | speaker | title | literature |
|---|---|---|---|
| Mon, Oct. 7, 2024 | all | Introduction and distribution of dates | |
| Mon, Oct. 14, 2024 | Giuseppe Romana | Generalizations of repetitiveness measures for 2D strings and their properties | Lorenzo Carafagna, Giovanni Manzini, Giuseppe Romana, Marinella Sciortino, and Cristian Urbina: Generalization of Repetitiveness Measures for Two-Dimensional Strings. SPIRE 2024. Paper |
| Mon, Oct. 21, 2024 | Francesco Masillo | A Textbook Solution for Dynamic Strings | Zsuzsanna Lipták, Francesco Masillo, and Gonzalo Navarro: A Textbook Solution for Dynamic Strings. ESA 2024. Paper |
| Mon, Oct. 28, 2024 | Alessio Campanelli | Where the Patterns Are: Repetition-Aware Compression for Colored de Bruijn Graphs | Alessio Campanelli, Giulio E. Pibiri, Jason Fan, and Rob Patro: Where the Patterns Are: Repetition-Aware Compression for Colored de Bruijn Graphs. (paper) |
| Mon, Nov. 4, 2024 | Davide Cenzato | An Introduction to Suffixient Sets | This is joint work with Francisco Olivares and Nicola Prezza. |
| Mon, Nov. 11, 2024 | Elena Biagi | Batched k-mer lookup on the Spectral Burrows-Wheeler Transform | Jarno N. Alanko, Elena Biagi, Joel Mackenzie, and Simon J. Puglisi: Batched k-mer lookup on the Spectral Burrows-Wheeler Transform. ALENEX 2025. Paper. |
| Mon, Nov. 18, 2024 | Marinella Sciortino | Exploring Repetitiveness in Texts: From BWT to Morphisms | This talk has been presented at the SPIRE 2024 conference. |
| Mon, Nov. 25, 2024 | Simone Lucà | Exploring Phylogenetic Networks | From the summer school CoPa - Computational Pangenomics - 2024 |
| Mon, Dec. 2, 2024 | Francesco Masillo | On Data Structures For Texts and Permutations | Mock PhD defence presentation |
| Mon, Dec. 9, 2024 | Zsuzsanna Lipták | A classical result on the Hamiltonicity of the graph of directed Euler tours of a given digraph G | Fu-ji Zhang and Xiao-feng Guo, Hamilton cycles in directed Euler tour graphs, Discr. Math. 1987. |
| Mon, Dec. 16, 2024 | Carlo Tosoni | Time-Space Efficient Graph Indices through BWT-Based Data Structures | |
| Mon, Jan. 13, 2025 | Ruben Becker | Embedding Edit into Hamming Distance with Small Distortion | Diptarka Chakraborty, Elazar Goldenberg, and Michal Koucký: Streaming algorithms for embedding and computing edit distance in the low distance regime. STOC 2016. |
| Mon, Jan. 20, 2025 | Luca Parmigiani | Degeneratigs: minimal representation of k-mers as degenerate strings is NP-hard | |
| Mon, Jan. 27, 2025 | Cristian Urbina | Revisiting the Lex-parse | Gonzalo Navarro, Carlos Ochoa, and Nicola Prezza: On the Approximation Ratio of Ordered Parsings. IEEE Transactions on Information Theory 2020. Yuto Nakashima, Dominik Köppl, Mitsuru Funakoshi, Shunsuke Inenaga, and Hideo Bannai: Edit and Alphabet-Ordering Sensitivity of Lex-Parse. MFCS 2024. |
List of talks of previous years: