CM1

Title: Text Indexing: How to Count via Reporting.

Abstract: I will present an elementary yet overlooked combinatorial lemma on strings. The lemma gives an upper bound on the number of substrings whose occurrences exceed their length. Together with its generalizations, the lemma has surprisingly broad consequences, leading to unified and improved results across a wide range of text indexing data structures.

Back to table

CM2

• 10.30-10.50: Travis Gagie. Merging RLBWTs adaptively
• 10.50-11.10: Gabriele Fici, Estéban Gabory, Giuseppe Romana and Marinella Sciortino. Totally Unclustered BWT Images of any Length over Non-Binary Alphabets
• 11.10-11.30: Paola Bonizzoni, Davide Cozzi and Younan Gao. Optimal-Time Mapping in Run-Length Compressed PBWT
• 11.30-11.50: Break
• 11.50-12.10: Jannik Olbrich and Enno Ohlebusch. The TAG array of a multiple sequence alignment
• 12.10-12:30: Kotaro Kimura and Tomohiro I. R-enum Revisited: Speedup and Extension for Context-Sensitive Repeats and Net Frequencies

Back to table

CM3

• 13.40-14.00: Soichiro Migita, Kyotaro Uehata and Tomohiro I. On the Smallest Size of Internal Collage Systems
• 14.00-14.20: Rikuya Hamai, Hiroto Fujimaru and Shunsuke Inenaga. Constant multiplicative sensitivity on the CDAWGs
• 14.20-14.40: Hideo Bannai, Yuto Fujie, Peaker Guo, Shunsuke Inenaga, Yuto Nakashima, Simon J. Puglisi and Cristian Urbina. Sensitivity of Repetitiveness Measures to String Reversal
• 14.40-15.00: Mutsunori Banbara, Hideo Bannai, Peaker Guo, Dominik Köppl, Takuya Mieno and Yoshio Okamoto. The Smallest String Attractors of Fibonacci and Period-Doubling Words

Back to table

CM4

• 15.30-15.50: Rahul Varki, Travis Gagie and Christina Boucher. Efficient Grammar Compression via RLZ-based RePair
• 15.50-16.10: Hiroki Shibata, Yuto Nakashima, Yutaro Yamaguchi and Shunsuke Inenaga. LZBE: an LZ-style compressor supporting O(log n)-time random access
• 16.10-16.30: Itai Boneh, Estéban Gabory, Pawel Gawrychowski and Adam Górkiewicz. Balancing Two-Dimensional Straight-Line Programs

Back to table

CT1

• 9.00-9.20: Moshe Lewenstein and Ely Porat. Set Parameterized Matching via Multi-Layer Hashing
• 9.20-9.40: Yuya Uezato. Matching Regular-Typed Pattern Languages: Quadratic-Time Algorithms
• 9.40-10.00: Carl Barton, Panagiotis Charalampopoulos, Taha El Ghazi, Jonas Ellert, Oded Lachish and Tatiana Starikovskaya. Periodicity Property Testing on Strings with Wildcards

Back to table

CT2

• 10.30-11.00: Highlight talk: Teresa Anna Steiner. Differentially Private Substring and Document Counting
• 11.00-11.10: Break
• 11.10-11.30: Itai Boneh, Dvir Fried, Shay Golan, Matan Kraus and Ely Porat. Hamming Distance Oracles
• 11.30-11.50: Tomasz Kociumaka, Jakob Nogler and Philip Wellnitz. The Communication Complexity of Pattern Matching with Edits Revisited
• 11.50-12.10: Diptarka Chakraborty, Rudrayan Kundu, Nidhi Purohit and Aravinda Kanchana Ruwanpathirana. Maximizing Diversity in (near-)Median String Selection
• 12.10-12.30: Michael Itzhaki, Amihood Amir, Ayelet Butman and Dina Sokol. On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and $k$-Errors

Back to table

CT3

• 13.40-14.00: Dominik Köppl and Gregory Kucherov. Near-real-time Solutions for Online String Problems
• 14.00-14.20: Wojciech Janczewski and Tatiana Starikovskaya. Asymmetric Streaming Approximate Pattern Matching
• 14.20-14.40: Paola Bonizzoni, Younan Gao and Brian Riccardi. Constructing Suffixient Arrays Revisited
• 14.40-15.00: Dmitry Kosolobov. Compressed Index with Construction in Compressed Space

Back to table

CW1/SW1

Title: From Strings to Planar Graphs and Back

Abstract: At the heart of various fundamental string problems (such as Edit Distance, Longest Common Subsequence, and Dynamic Time Warping) lies the challenge of computing distances in a grid-like graph called the alignment graph. Historically, techniques that were developed for computing distances in the alignment graph were later extended to general planar graphs. These techniques include multiple-source shortest-paths (MSSP), the Monge property, and compression. Surprisingly, the flow of techniques has been bidirectional. Namely, powerful techniques like Voronoi diagrams and dynamic all-pairs shortest-paths (APSP) were first pioneered in the broader realm of planar graphs and only then specialized to the alignment graph. In my talk, I will survey this remarkable cross-fertilization between planar graph algorithms and string algorithms.

Back to table

CW2

• 10.30-10.50: Takuya Mieno. Compact representation of maximal palindromes
• 10.50-11.10: Arkadiusz Czarkowski. Improved Bounds on the Sum of Exponents of Runs in a String
• 11.10-11.30: Panagiotis Charalampopoulos, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen and Wiktor Zuba. Improved Bounds on the Maximum Number of Distinct Squares in Circular Words
• 11.30-11.50: Break
• 11.50-12.10: Kaisei Kishi, Peaker Guo, Cristian Urbina and Hideo Bannai. On Occurrence-Preserving Morphisms
• 12.10-12.30: Shay Golan, Matan Kraus, Ely Porat and Braha Riva Shalom. Exploring the Gap Between LCS and LCStr

Back to table

CW3

• 13.40-14.00: Pawel Gawrychowski, Florin Manea and Jonas Richardsen. Optimal Structure for Prefix-Substring Queries
• 14.00-14.20: Johannes Fischer and Filippo Lari. Indexing and Encoding Arrays for Element Distinctness Queries
• 14.20-14.40: Daniel Albert. Longest Common Extension of a Dynamic String in Parallel Constant Time
• 14.40-15.00: Po-Chun Chen, Che-Wei Tsao, Wing-Kai Hon and Dominik Köppl. Efficient Index for Square Pattern Matching

Back to table

CW4

• 15.30-15.50: Jarno Alanko and Máximo Pérez López. Computing k-mers in Graphs
• 15.50-16.10: Dominik Köppl and Jannik Olbrich. Hardness Results on Characteristics for Elastic-Degenerated Strings
• 16.10-16.30: Simone Faro, Dominik Köppl, Thierry Lecroq and Francesco Pio Marino. A Bitwise Approach to SCER Matching in Indeterminate Strings
• 16.30-16.50: Ryosuke Yamano and Tetsuo Shibuya. Improved Approximation Ratios for the Shortest Common Superstring Problem with Reverse Complements

Back to table