https://www.dagstuhl.de/20415

05. – 08. Oktober 2020, Event 20415

New Results in Text Algorithmics and Combinatorics on Strings

Organisator

Johannes Fischer (TU Dortmund, DE)

Auskunft zu diesem Event erteilt

Heike Clemens

Description

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.

Bibliography

  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

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact aufgelistet und separat in der Bibliothek präsentiert.