Preliminary Program:

All times are in Copenhagen time (CEST)

Wednesday, June 17, 2020

8:50 - 9:00

Opening Remarks

 

Invited Talk I (Chair: Inge Li Gørtz)

9:00 - 10:00

Thore Husfeldt

Algebraic algorithms for finding patterns in graphs (video)

 

10:00 - 10:20

Break

 

Session I (Chair: Gadi Landau)

10:20 - 10:45

Evangelos Kipouridis and Kostas Tsichlas.

Longest Common Subsequence on Weighted Sequences

(video, slides)

Recipient of the Best Paper Award

10:45 - 11:10

Stav Ben-Nun, Shay Golan, Tomasz Kociumaka and Matan Kraus.

Time-Space Tradeoffs for Finding a Long Common Substring (video)

11:10 - 11:35

Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski and Tatiana Starikovskaya.

Approximating longest common substring with k mismatches: Theory and practice (video, slides)

 

11:35 - 11:55

Break

 

Session II (Chair: Panagiotis Charalampopoulos)

11:55 - 12:20

Giulia Bernardini, Huiping Chen, Grigorios Loukides, Nadia Pisanti, Solon Pissis, Leen Stougie and Michelle Sweering.

String Sanitization under Edit Distance (video)

12:20 - 12:45

Veli Mäkinen and Kristoffer Sahlin.

Chaining with Overlaps Revisited (video)

12:45 - 13:10

Przemysław Uznański.

Approximating Text-to-Pattern distance via dimensionality reduction (video, slides)

13:10 - 14:30

Lunch

Highlight Talk I (Chair: Oren Weimann)

14:30 - 15:00

Paweł Gawrychowski

Computing Quartet Distance is Equivalent to Counting 4-Cycles (video)

 

Session III (Chair: Jakub Radoszewski)

15:00 - 15:25

Kotaro Matsuda, Kunihiko Sadakane, Tatiana Starikovskaya and Masakazu Tateshita.

Compressed Orthogonal Search on Suffix Arrays with applications to Range LCP (video, slides)

15:25 - 15:50

Arnab Ganguly, Daniel Gibney, Sahar Hooshmand, M. Oğuzhan Külekci and Sharma V. Thankachan.

FM-Index Reveals the Reverse Suffix Array (video, slides)

 

15:50 - 16:10

Break

 

Session IV (Chair: Nicola Prezza)

16:10 - 16:35

Patty Commins, David Liben-Nowell, Tina Liu and Kiran Tomlinson.

Summarizing Diverging String Sequences, with Applications to Chain-Letter Petitions (video, slides)

16:35 - 17:00

Julian Pape-Lange.

On Extensions of Maximal Repeats in Compressed Strings (slides)

 

17:00 - 17:30

Business Meeting

Thursday, June 18, 2020

Invited Talk II (Chair: Danny Hermelin)

9:00 - 10:00

Karl Bringmann

Fine-Grained Complexity on Strings (video, slides)

 

10:00 - 10:20

Break

 

Session V (Chair: Solon Pissis)

10:20 - 10:45

Panagiotis Charalampopoulos, Tomasz Kociumaka and Shay Mozes. Dynamic String Alignment (video, slides)

10:45 - 11:10

Dominik Köppl, Daiki Hashimoto, Diptarama Hendrian and Ayumi Shinohara.

In-Place Bijective Burrows Wheeler Transformations (video)

11:10 - 11:35

Panagiotis Charalampopoulos, Solon Pissis, Jakub Radoszewski, Tomasz Walen and Wiktor Zuba.

Unary Words Have the Smallest Levenshtein k-Neighbourhoods

(video, slides)

 

11:35 - 11:55

Break

 

Session VI (Chair: Przemysław Uznański)

11:55 - 12:20

Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz and Ely Porat.

The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time (video, slides)

12:20 - 12:45

Paweł Gawrychowski, Samah Ghazawi and Gad M. Landau.

On Indeterminate Strings Matching (video, slides)

12:45 - 13:10

Katsuhito Nakashima, Noriki Fujisato, Diptarama Hendrian, Yuto Nakashima, Ryo Yoshinaka, Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara and Masayuki Takeda.

DAWGs for parameterized matching: online construction and related indexing structures (video)

 

13:10 - 14:30

Lunch

 

Highlight Talk II (Chair: Oren Weimann)

14:30 - 15:00

Shay Golan

Locally Consistent Parsing for Text Indexing in Small Space

(video, slides)

 

Session VII (Chair: Zsuzsanna Lipták)

15:00 - 15:25

Giulia Bernardini, Paola Bonizzoni and Paweł Gawrychowski

On Two Measures of Distance between Fully-Labelled Trees

(video, slides)

15:25 - 15:50

Djamal Belazzougui and Gregory Kucherov.

Efficient tree-structured categorical retrieval (video)

Friday, June 19, 2020

Highlight Talk III (Chair: Inge Li Gørtz)

9:00 - 9:30

Tomasz Kociumaka

String synchronizing sets: Sublinear-time BWT construction and optimal LCE data structure (video)

 

9:30 – 9:50

Break

 

Session VIII (Chair: Philip Bille)

9:50 – 10:15

Ian Munro, Gonzalo Navarro and Yakov Nekrich.

Text Indexing and Searching in Sublinear Time (video, slides)

10:15 – 10:40

Amihood Amir, Ayelet Butman, Gad M. Landau, Shoshana Marcus and Dina Sokol. Double String Tandem Repeats (video, slides)

10:40 – 11:05

Aleksander Kędzierski and Jakub Radoszewski.

k-Approximate Quasiperiodicity under Hamming and Edit

Distance (video, slides)

 

11:05 – 11:25

Break

 

Session IX (Chair: Amihood Amir)

11:25 - 11:50

Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń and Wiktor Zuba.

Counting Distinct Patterns in Internal Dictionary Matching (video)

11:50 – 12:15

Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda and Ayumi Shinohara.

Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences (slides)

12:15 – 12:40

Mai Alzamel, Alessio Conte, Shuhei Denzumi, Roberto Grossi, Costas Iliopoulos, Kazuhiro Kurita and Kunihiro Wasa.

Finding the Anticover of a String (video)

12:40 - 13:05

Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz and Frank Sommer.

String Factorizations under Various Collision Constraints

(video, slides)

 

13:05 - 14:35

Lunch

 

Session X (Chair: Artur Jeż)

14:35 - 15:00

Nathan Schaar, Vincent Froese and Rolf Niedermeier.

Faster Binary Mean Computation Under Dynamic Time Warping (video, slides)

15:00 - 15:25

Tomohiro Koana, Vincent Froese and Rolf Niedermeier.

Parameterized Algorithms for Matrix Completion With Radius Constraints (video)

15:25 - 15:50

Manuel Lafond, Binhai Zhu and Peng Zou.

Genomic Problems Involving Copy Number Profiles: Complexity and Algorithms (video, slides)

 

15:50 – 16:10

   Break

 

Invited Talk III (Chair: Amir Abboud)

16:10 – 17:10

Barna Saha

Efficient Fine-grained Algorithms (video)

 

17:10 – 17:15

Closing Remarks