Research Meeting 20415
New Results in Text Algorithmics and Combinatorics on Strings
( Oct 05 – Oct 08, 2020 )
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/20415
Organizer
- Johannes Fischer (TU Dortmund, DE)
Contact
- Heike Clemens (for administrative matters)
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
-
M. A. Bender, R. Das, M. Farach-Colton, R. Johnson, and W. Kuszmaul.
Flushing without cascades.
In SODA, pages 650–669. SIAM, 2020. -
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. -
P. Bille and I. L. Gørtz.
Random access in persistent strings.
CoRR, abs/2006.15575, 2020. -
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. -
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. -
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. -
M. Ganardi, A. Jez, and M. Lohrey.
Balancing straight-line programs.
In FOCS, pages 1169–1183. IEEE Computer Society, 2019. -
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. -
V. Jugé.
Adaptive Shivers sort: An alternative sorting algorithm.
In SODA, pages 1639–1654. SIAM, 2020. -
D. Kempa and T. Kociumaka.
Resolution of the Burrows-Wheeler transform conjecture.
CoRR, abs/1910.10631, 2019. -
H. Yu.
Nearly optimal static Las Vegas succinct dictionary.
In STOC, pages 1389–1401. ACM, 2020.
Creative Commons BY 3.0 DE
Johannes Fischer
