Keynote speakers

    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.

    Image of Alexandra Lassota
  • Alexandra Lassota (Eindhoven Technical University (TU/e))

    • Title: Finding the very best committee

    Abstract: Selecting the single best winner in an election can be difficult, sometimes even impossible. In this talk, I will show that selecting just six winners is always sufficient to achieve a majority approval: they form what is known as a Condorcet winning set. I will also discuss how this number can be reduced for a natural class of instances that are 2-D embeddable. Finally, I will present algorithms for finding the optimal committee under various Thiele rules. These are joint works with an amazing set of coauthors: Moses Charikar, Prasanna Ramakrishnan, Ulrike Schmidt-Kraepelin, Krzysztof Sornat, Bernhard von Stengel, Adrian Vetta, and Kangning Wang.