October 5 – 8 , 2020, Event 20415

New Results in Text Algorithmics and Combinatorics on Strings


Johannes Fischer (TU Dortmund, DE)

For support, please contact

Heike Clemens


In the research group meeting 20415 "New Results in Text Algorithmics and Combinatorics on Strings" at Schloss Dagstuhl, we presented and discussed several recently published papers from leading venues in Theoretical Computer Science.

We covered topics like text algorithmics and combinatorics on strings [5,4,6,3,7], text compression 10], dictionaries [11], graph coloring [2], sorting [9], external-memory search trees [1], and geometric data structures [8]. Each paper was presented in a blackboard presentation of at least 90 minutes.


  1. M. A. Bender, R. Das, M. Farach-Colton, R. Johnson, and W. Kuszmaul.
    Flushing without cascades.
    In SODA, pages 650–669. SIAM, 2020.
  2. S. K. Bera, A. Chakrabarti, and P. Ghosh.
    Graph coloring via degeneracy in streaming and other space-conscious models.
    In ICALP, volume 168 of LIPIcs, pages 11:1–11:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  3. P. Bille and I. L. Gørtz.
    Random access in persistent strings.
    CoRR, abs/2006.15575, 2020.
  4. P. Bille, I. L. Gørtz, and T. A. Steiner.
    String indexing with compressed patterns.
    In STACS, volume 154 of LIPIcs, pages 10:1–10:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  5. T. M. Chan, S. Golan, T. Kociumaka, T. Kopelowitz, and E. Porat.
    Approximating text-to-pattern Hamming distances.
    In STOC, pages 643–656. ACM, 2020.
  6. P. Charalampopoulos, J. Radoszewski, W. Rytter, T. Walen, and W. Zuba.
    The number of repetitions in 2d-strings.
    In ESA, volume 173 of LIPIcs, pages 32:1–32:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  7. M. Ganardi, A. Jez, and M. Lohrey.
    Balancing straight-line programs.
    In FOCS, pages 1169–1183. IEEE Computer Society, 2019.
  8. Y. Gao, M. He, and Y. Nekrich.
    Fast preprocessing for optimal orthogonal range reporting and range successor with applications to text indexing.
    In ESA, volume 173 of LIPIcs, pages 54:1–54:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  9. V. Jugé.
    Adaptive Shivers sort: An alternative sorting algorithm.
    In SODA, pages 1639–1654. SIAM, 2020.
  10. D. Kempa and T. Kociumaka.
    Resolution of the Burrows-Wheeler transform conjecture.
    CoRR, abs/1910.10631, 2019.
  11. H. Yu.
    Nearly optimal static Las Vegas succinct dictionary.
    In STOC, pages 1389–1401. ACM, 2020.

Motivation text license
  Creative Commons BY 3.0 DE
  Johannes Fischer

Online Publications

We offer several possibilities to publish the results of your event. Please contact publishing(at) if you are interested.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf in the library.