List of talks of previous years:
| date | speaker | title | literature |
|---|---|---|---|
| Mon, Feb. 21, 2022 | Davide Cenzato | On different variants of the Burrows-Wheeler-Transform for string collections | practice talk for DCC 2022 poster session. |
| Mon, Feb. 28, 2022 | --- | (Carnival) | |
| Mon, March 7, 2022 | Marinella Sciortino | Words generated by morphisms: some combinatorial properties | Sorin Constantinescu, Lucian Ilie:
The Lempel--Ziv Complexity of Fixed Points of Morphisms. SIAM J. Discret. Math. 21(2): 466-481 (2007), and Luke Schaeffer, Jeffrey O. Shallit: String Attractors for Automatic Sequences. CoRR abs/2012.06840 (2020) |
| Mon, March 14, 2022 | Giuseppe Romana | Burrows-Wheeler transform and purely morphic finite words | Andrea Frosini, Ilaria Mancini, Simone Rinaldi, Giuseppe Romana, Marinella Sciortino: Logarithmic equal-letter runs for BWT of purely morphic words. Accepted for presentation at DLT 2022. See here for Arxiv version of paper: Arxiv. |
| Mon, March 21, 2022 | Zsuzsanna Lipták | On feasible permutations | A side result from our paper: Davide Cenzato and Zsuzsanna Lipták: A theoretical and experimental analysis of BWT variants for string collections (2022). See here for Arxiv version of paper: Arxiv (update 31 March: paper accepted at CPM 2022). |
| Mon, March 28, 2022 | Sara Giuliani | LZ-factorization of regular sampling of a string | ongoing work |
| Mon, April 4, 2022 | Francesco Masillo | On the suffix array construction algorithm DivSufSort | J. Fischer, F. Kurpicz: Dismantling DivSufSort. Stringology 2017: 62-76. See paper or Arxiv version. |
| Mon, April 11, 2022 | Davide Cenzato | The XBWT of string collections | Giovanni Manzini: XBWT Tricks. SPIRE 2016: 80-92. See paper. |
| Mon, April 18, 2022 | --- | (Easter) | |
| Mon, April 25, 2022 | --- | (Public Holiday) | |
| Mon, May 2, 2022 | Andrea Caucchiolo | A Polynomial Time Approximation Scheme for MAX-CUT on Dense Graphs | S. Arora, D. R. Karger, M. Karpinski: Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems. J. Comput. Syst. Sci. 58(1): 193-210 (1999), see here. |
| Mon, May 9, 2022 | Elena Biagi | Experiments on the BBWT | ongoing work (master thesis) |
| Mon, May 16, 2022 | Luca Parmigiani | The equivalence of MAX-ECD and MAX-ACD and the complexity of MIN-SBR (part 1) | A. Caprara: Sorting Permutations by Reversals and Eulerian Cycle Decompositions. SIAM J. Discret. Math. 12(1): 91-110 (1999) |
| Mon, May 23, 2022 | Luca Parmigiani | The equivalence of MAX-ECD and MAX-ACD and the complexity of MIN-SBR (part 2) | (same as last week) |
| Mon, May 30, 2022 | --- | ||
| Mon, June 6, 2022 | Andrea Caucchiolo | On the Intractability Landscape of Digraph Intersection Representations | Andrea Caucchiolo, Ferdinando Cicalese: On the Intractability Landscape of Digraph Intersection Representations. To be presented at: IWOCA 2022, Trier, Germany, June 7-9, 2022, see here. |
| Mon, June 13, 2022 | --- | ||
| Mon, June 20, 2022 | Davide Cenzato | A theoretical and experimental analysis of BWT variants for string collections | Davide Cenzato and Zsuzsanna Lipták: A theoretical and experimental analysis of BWT variants for string collections, to be presented at: 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), Prague, 27-29 June, 2022. Paper see here. |
| Mon, June 27, 2022 | --- | (CPM in Prague) | |
| Mon, July 4, 2022 | --- | (Lake Como School on Pangenomics) | |
| Mon, July 11, 2022 | Elena Biagi | Experiments on the Bijective Burrows-Wheeler-Transform | (mock laurea talk) |
| Mon, July 18, 2022 | Giuseppe Romana | Computing Maximal Unique Matches with the r-index | Sara Giuliani, Giuseppe Romana, and Massimiliano Rossi: Computing Maximal Unique Matches with the r-index. To be presented at the 20th Symposium on Experimental Algorithms (SEA 2022), Heidelberg, Germany, 25-27 July 2022. |
| date | speaker | title | literature |
|---|---|---|---|
| Mon, Sept. 13, 2021 | Andrea Caucchiolo | Hardness of MSA with Selective Column Scoring | A. Caucchiolo and F. Cicalese: Hardness of MSA with Selective Column Scoring. To appear in: Proc. of the 22nd Italian Conference on Theoretical Computer Science (ICTCS 2021), Bologna, Italy, 13-15 Sept. 2021. |
| Mon, Sept. 27, 2021 | Davide Cenzato | Computing the original eBWT faster, simpler, and with less memory |
C. Boucher, D. Cenzato, Zs. Lipták, M. Rossi, M. Sciortino: Computing the original eBWT faster, simpler, and with less memory. To appear in: Proc. of the 28th Int. Symp. on String Processing and Information Retrieval (SPIRE 2021), Lille, France, October 4-6, 2021, LNCS 12944: 129-142 (2021). For the Arxiv version, see here. |
| Mon, Oct. 4, 2021 | Giuseppe Romana | Online MUMs with PHONI | S. Giuliani, G. Romana, M. Rossi: Online MUMs with PHONI. Abstract to be presented at the 16th Workshop on Compression, Text and Algorithms (WCTA 2021) |
| Mon, Oct. 11, 2021 | Davide Canevazzi | 1. (mock laurea talk) 2. Some experiments on strings |
master thesis (group Delledonne), and internship with us on string algorithms |
| Mon, Oct. 18, 2021 | Eva Viesi | Exploring clustering stability of emerging tools for the analysis of spatial transcriptomics data | master thesis (group Giungo) |
| Mon, Oct. 25, 2021 | Francesco Masillo | Adapting tools for the Hamming distance to pseudo-local metrics | Avivit Levy: Exploiting Pseudo-locality of Interchange Distance, SPIRE 2021 link. |
| Mon, Nov. 15, 2021 | Francesco Masillo | Adapting tools for the Hamming distance to pseudo-local metrics (part 2) | |
| Mon, Nov. 22, 2021 | Luca Parmigiani | Construction and indexing of Colored Compacted de Bruijn graphs with Bifrost. | Holley, G., Melsted, P. Bifrost: highly parallel construction and indexing of colored and compacted de Bruijn graphs. Genome Biol 21, 249 (2020). link to paper |
| Mon, Nov. 29, 2021 | Davide Cenzato | On updating the BWT | Mikaäl Salson, Thierry Lecroq, Martine Léonard, Laurent Mouchard: A four-stage algorithm for updating a Burrows-Wheeler transform. Theor. Comput. Sci. 410(43): 4350-4359 (2009) |
| Mon, Dec. 20, 2021 | Massimiliano Rossi | MONI: Design Challenges for a Pangenomic Tool | tool availalbe at: github.com/maxrossi91/moni |
| Mon, Dec. 20, 2021 | Davide Cenzato | Relative LZ compression of Suffix Arrays, by Puglisi & Zhukova | Simon J. Puglisi, Bella Zhukova:
Relative Lempel-Ziv Compression of Suffix Arrays. SPIRE 2020: 89-96, and Simon J. Puglisi, Bella Zhukova: Smaller RLZ-Compressed Suffix Arrays. DCC 2021: 213-222 |
| Mon, Jan. 10, 2021 | Francesco Masillo | On the suffix array construction algorithm GSACA | Uwe Baier:
Linear-time Suffix Sorting - A New Approach for Suffix Array Construction. CPM 2016: 23:1-23:12, and Frantisek Franek, Asma Paracha, and William F. Smyth: The Linear Equivalence of the Suffix Array and the Partially Sorted Lyndon Array, PSC 2017:77-84. |
| Mon, Jan. 17, 2021 | Andrea Caucchiolo | (In)Approximability of MSA with Column Score |
Click here for last year's Monday meetings (2020/2021), or for
the previous year (2019/2020).