CPM 2024

35th Annual Symposium on Combinatorial Pattern Matching

Fukuoka, Japan, June 25–27, 2024

Programme

    Skip to day:
  1. Tuesday
  2. Wednesday
  3. Thursday

Tuesday, June 25, 2024

08:30 - 08:50Registration
08:50 - 09:00Opening
Keynote Talk 1 (Chair: Hideo Bannai)
09:00 - 10:00

Tetsuo Shibuya

Preserving Privacy in Biomedical Data with “More Efficient” Differentially Private Algorithms (slides)
10:00 - 10:20Coffee break
Contributed talks 1 [compression and alphabet ordering]
(Chair: Nicola Prezza)
10:20 - 10:40

Hideo Bannai, Panagiotis Charalampopoulos and Jakub Radoszewski.

Maintaining the Size of LZ77 on Semi-dynamic Strings (slides)
10:40 - 11:00

Zsuzsanna Liptak, Francesco Masillo and Gonzalo Navarro.

BAT-LZ out of Hell (slides)
11:00 - 11:20

Philip Bille, Christian Mikkelsen Fuglsang and Inge Li Gørtz.

Tight Bounds for Compressing Substring Samples
11:20 - 11:40

Gianmarco Bertola, Anthony J. Cox, Veronica Guerrini and Giovanna Rosone.

A class of heuristics for reducing the number of BWT-runs in the String Ordering Problem (slides)
11:40 - 12:00

Hilde Verbeek, Lorraine Ayad, Grigorios Loukides and Solon Pissis.

Minimizing the Minimizers via Alphabet Reordering (slides)
12:00 - 14:00Lunch break
Highlight Talk 1 (Chair: Gonzalo Navarro)
14:00 - 14:30

Philip Bille

Gapped String Indexing in Subquadratic Space and Sublinear Query Time (STACS 2024) (slides)
Contributed talks 2 [space-efficient algorithms]
(Chair: Gonzalo Navarro)
14:30 - 14:50

Gabriel Bathie, Panagiotis Charalampopoulos and Tatiana Starikovskaya.

Internal Pattern Matching in Small Space and Applications (slides)
14:50 - 15:10

Paola Bonizzoni, Christina Boucher, Davide Cozzi, Travis Gagie and Yuri Pirola.

Solving the Minimal Positional Substring Cover problem in sublinear space. (slides)
15:10 - 15:30

Dmitry Kosolobov and Nikita Sivukhin.

Construction of Sparse Suffix Trees and LCE Indexes in Optimal Time and Space (slides)
15:30 - 15:50Coffee break
Contributed talks 3 [algorithms on string graphs 1]
(Chair: Tomohiro I)
15:50 - 16:10

Giovanni Manzini, Alberto Policriti, Nicola Prezza and Brian Riccardi.

The rational construction of a Wheeler DFA (slides)
16:10 - 16:30

Ruben Becker, Davide Cenzato, Sung-Hwan Kim, Bojana Kodric, Riccardo Maso and Nicola Prezza.

Random Wheeler Automata (slides)
16:30 - 16:50

Giulia Bernardini, Huiping Chen, Inge Li Gørtz, Christoffer Krogh, Grigorios Loukides, Solon Pissis, Leen Stougie and Michelle Sweering.

Connecting de Bruijn Graphs (slides)
16:50 - 17:10

Jarno Alanko, Davide Cenzato, Nicola Cotumaccio, Sung-Hwan Kim, Giovanni Manzini and Nicola Prezza.

Computing the LCP Array of a Labeled Graph (slides)
17:10 - 17:20Mini break
17:20 - 18:20Business meeting

Back to top

Wednesday, June 26, 2024

Keynote Talk 2 (Chair: Shunsuke Inenaga)
09:00 - 10:00

Zsuzsanna Lipták

BWT everywhere (slides)
10:00 - 10:20Coffee break
Contributed talk 4 [string algorithms and data structures]
(Chair: Philip Wellnitz)
10:20 - 10:40

Bartlomiej Dudek and Pawel Gawrychowski.

Online Context-Free Recognition in OMv Time (slides)
10:40 - 11:00

Philip Bille, Pawel Gawrychowski, Inge Li Gørtz and Simon R. Tarnow.

Faster Sliding Window String Indexing in Streams (slides)
11:00 - 11:20

Kazuki Mitani, Takuya Mieno, Kazuhisa Seto and Takashi Horiyama.

Shortest cover after edit (slides)
11:20 - 11:40

Yoshifumi Sakai.

A data structure for the maximum-sum segment problem with offsets (slides)
11:40 - 12:00

Dmitry Kosolobov.

Simplified Tight Bounds for Monotone Minimal Perfect Hashing (slides)
12:00 - 13:00Lunch break at conference venue
13:00 - 18:30Excursion
18:30 - 21:00Conference dinner

Back to top

Thursday, June 27, 2024

Keynote Talk 3 (Chair: Simon J. Puglisi)
09:00 - 10:00

Martin Farach-Colton

How Big is a Pointer? (slides)
10:00 - 10:20Coffee break
Highlight Talk 2 (Chair: Simon J. Puglisi)
10:20 - 10:50

Yasuo Tabei

Optimal-Time Queries on BWT-Runs Compressed Indexes (ICALP 2021)
An Optimal-Time RLBWT Construction in BWT-Runs Bounded Space (ICALP 2022) (slides)
Contributed talks 5 [algorithms on string graphs 2]
(Chair: Jarno Alanko)
10:50 - 11:10

Yuto Shida, Giulia Punzi, Yasuaki Kobayashi, Takeaki Uno and Hiroki Arimura.

Finding Diverse Strings and Longest Common Subsequences in a Graph (slides)
11:10 - 11:30

Meng He and Kaiyu Wu.

Closing the Gap: Minimum Space Optimal Time Distance Labeling Scheme for Interval Graphs (slides)
11:30 - 11:50

Michael Itzhaki and Amihood Amir.

Reconstructing General Matching Graphs
11:50 - 14:00Lunch break
Contributed talks 6 [string comparison and 2D strings]
(Chair: Dmitry Kosolobov)
14:00 - 14:20

Dana Fisman and Ilay Tzarfati.

When is the Normalized Edit Distance over Non-Uniform Weights a Metric? (slides)
14:20 - 14:40

Florin Manea, Jonas Richardsen and Markus L. Schmid.

Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds (slides)
14:40 - 15:00

Itai Boneh, Dvir Fried, Shay Golan and Matan Kraus.

Hairpin Completion Distance Lower Bound
15:00 - 15:20

Itai Boneh, Dvir Fried, Shay Golan, Matan Kraus, Adrian Miclaus and Arseny Shur.

Searching 2D-Strings for Matching Frames (slides)
15:20 - 15:40Coffee break
Contributed talks 7 [string combinatorics and algorithms]
(Chair: Gabriele Fici)
15:40 - 16:00

Peaker Guo, Patrick Eades, Anthony Wirth and Justin Zobel.

Exploiting New Properties of String Net Frequency for Efficient Computation (slides)
16:00 - 16:20

Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka and Ayumi Shinohara.

Algorithms for Galois Words: Detection, Factorization, and Rotation (slides)
16:20 - 16:40

Ian Pratt-Hartmann.

Walking on words (slides)
16:40 - 17:00

Daniel Gabric and Joe Sawada.

Efficient construction of long orientable sequences (slides)
17:00 - 17:10Closing

Lunches are not provided on 25th and 27th.

Back to top