Keynote speakers

    Image of Solon P. Pissis
  • Solon P. Pissis (The Cyprus Institute)

    • Title: Text Indexing: How to Count via Reporting

    Abstract: I will present an elementary yet overlooked combinatorial lemma on strings. The lemma gives an upper bound on the number of substrings whose occurrences exceed their length. Together with its generalizations, the lemma has surprisingly broad consequences, leading to unified and improved results across a wide range of text indexing data structures.

    Image of Oren Weimann
  • Oren Weimann (University of Haifa, Israel)

    • Title: From Strings to Planar Graphs and Back

    Abstract: At the heart of various fundamental string problems (such as Edit Distance, Longest Common Subsequence, and Dynamic Time Warping) lies the challenge of computing distances in a grid-like graph called the alignment graph. Historically, techniques that were developed for computing distances in the alignment graph were later extended to general planar graphs. These techniques include multiple-source shortest-paths (MSSP), the Monge property, and compression. Surprisingly, the flow of techniques has been bidirectional. Namely, powerful techniques like Voronoi diagrams and dynamic all-pairs shortest-paths (APSP) were first pioneered in the broader realm of planar graphs and only then specialized to the alignment graph. In my talk, I will survey this remarkable cross-fertilization between planar graph algorithms and string algorithms.