Wiktor Zuba and Solon Pissis from CWI’s Networks & Optimization group were awarded the Best Paper Award of SPIRE 2022, the 2022 Symposium on String Processing and Information Retrieval conference in Concepción, Chile. They won the award together with Panagiotis Charalampopoulos (Birkbeck, University of London), Jakub Radoszewski, Wojciech Rytter and Tomasz Walen (University of Warsaw) for their paper ‘Subsequence Covers of Words’. This theoretical research has potential applications in bioinformatics and data compression.
In combinatorics and computer science, covering problems are basic problems asking whether a combinatorial structure like a network or a string can be covered by another one. In their winning paper, the authors studied the notion of string covering. Covering one string with another string helps to unveil various regularities. The authors show that covering a string with subsequence occurrences of another string can be done in a reasonable time (‘linear time’) in the case when they are allowed to overlap. This result shows a clear separation from the case when such overlaps are not permitted. In the latter case the problem is unfortunately known to be not tractable. A video presentation about the paper ‘Subsequence Covers of Words’ by Wiktor Zuba is available online.
This picture shows how the string in black can be covered by subsequence occurrences of the string in blue.
About the SPIRE conference
SPIRE is the annual Symposium on String Processing and Information Retrieval. SPIRE has its origins in the South American Workshop on String Processing, which was first held in Belo Horizonte, Brazil, in 1993. Since 1998 the focus of the workshop has also included information retrieval, due to its increasing relevance to and inter-relationship with string processing. The Best Paper Award was announced on 10 November.
More information
- The Networks and Optimization group at CWI
- SPIRE 2022 Conference
- A video presentation about the paper ‘Subsequence Covers of Words’ by Wiktor Zuba: https://www.youtube.com/watch?v=zftXJJElssU (approximately from the start until ca. 19 min.)
- Contact information of Wiktor Zuba (CWI) and Solon Pissis (CWI and VU)
SPIRE 2022 Best Paper Award winners Wiktor Zuba and Solon Pissis. They share the prize with their four co-authors.
