Click here for the current academic year.
The Monday meetings of the 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 (other cities, other countries, or even on other continents!)
Working language is English. If you are interested in participating, send me an email.
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).