CW1/SW1

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.

Back to table

SW2

• 10.30-10.50: Chirag Kaudan and Amir Nayyeri. Cutwidth versus BFS-Width with Applications to Graph Reconstruction from Distance Queries
• 10.50-11.10: Ovidiu Rață. Faster Linear-Space Data Structures for Path Frequency Queries
• 11.10-11.30: Seungbum Jo and Dominik Köppl. Indexing Range Maximum-Sum Segment Queries with Offsets
• 11.30-11.40: Break
• 11.40-12.00: Júlia Baligács, Yann Disser and Linda Thelen. Improved Bounds for Online TSP on the Half-Line
• 12.00-12.20: Minati De, Satyam Singh and Csaba Tóth. Online Hitting Set for Axis-Aligned Squares
• 12.20-12.40: Avinandan Das. One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming

Back to table

SW3

• 13.40-14.00: Ronald Deng, Samuel McCauley, Aidin Niaparast, Helia Niaparast, Bennett Ptak, Shirel Quintanilla, Shikha Singh and Nathan Vosburg. Incremental Strongly Connected Components with Predictions
• 14.00-14.20: Indu Ramesh, Boris Aronov, Mayank Goswami and John Iacono. On the Fragile Complexity of Geometric Algorithms
• 14.20-14.40: Tiziana Calamoneri, Pierre Gaillard, Giacomo Paesani and Giuseppe Perelli. Strategy Repair in Reachability Games via a Graph Quotientation
• 14.40-15.00: Kengo Nakamura and Masaaki Nishino. Linear-Time Exact Computation of Influence Spread on Bounded-Pathwidth Graphs

Back to table

SW4

• 15.30-15.50: Konstanty Junosza-Szaniawski, Antonio Lauerbach, Marie Diana Sieper and Alexander Wolff. The Parameterized Complexity of Coloring Mixed Graphs
• 15.50-16.10: Jie Gao, Pawel Gawrychowski, Panos Giannopoulos, Wolfgang Mulzer, Satyam Singh, Frank Staals and Meirav Zehavi. Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs
• 16.10-16.30: Jaehoon Chung. Orthogonal Strip Partitioning of Polygons: Lattice-Theoretic Algorithms and Lower Bounds
• 16.30-16.50: Alma Arevalo Loyola, Ahmad Biniaz and Prosenjit Bose. Polychromatic 2-colorings with Bounded Discrepancy for Triangulations

Back to table

ST1

• 9.00-9.20: Robert Barish and Tetsuo Shibuya. Arranging pairwise disjoint shapes to partition point sets
• 9.20-9.40: Seongbin Park and Eunjin Oh. Exact Subquadratic Algorithm for Many-to-Many Matching on Planar Point Sets with Integer Coordinates
• 9.40-10.00: Jaegun Lee, Chaeyoon Chung and Hee-Kap Ahn. Bichromatic Classifications of Points using Strips

Back to table

ST3

• 13.40-14.00: Panagiotis Charalampopoulos, Manal Mohamed, Solon Pissis, Hilde Verbeek and Wiktor Zuba. Faster Algorithms for Unique or Absent Substrings
• 14.00-14.20: Liam Roditty and Plia Trabelsi. New algorithms for girth and cycle detection
• 14.20-14.40: Bart M. P. Jansen and Ruben F.A. Verhaegh. Search-space Reduction for Boolean MinCSPs via Essential Constraints
• 14.40-15.00: Michal Moiseev, Omrit Filtser and Tzalik Maimon. On Fréchet Traveling Salesmen Problems

Back to table

ST4

• 15.30-15.50: Pankaj Kumar, Haiku Muller, Sebastian Ordyniak and Melanie Schmidt. On the Parameterized Complexity of Min-Sum-Radii
• 15.50-16.10: Aditya Acharya, Auguste Gezalyan and David Mount. Classifiers in High Dimensional Hilbert Metrics
• 16.10-16.30: Young-San Lin and Alexander Turoczy. Improved and Parameterized Algorithms for Online Multi-level Aggregation: A Memory-based Approach
• 16.30-16.40: Break
• 16.40-17.00: Michael Levet. Parallel Algorithms for Group Isomorphism via Code Equivalence
• 17.00-17.20: Kimon Boehmer. Submodular Max-Min Allocation under Identical Valuations (best student-paper award)
• 17.20-17.40: Ofer Neiman and Alon Spector. Path-Reporting Distance Oracles for Vertex-Labeled Graphs

Back to table

SF1

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.

Back to table

SF2

• 10.30-10.50: Suruchi Kushwaha and Yakov Nekrich. New Results on Three-Sided Skyline Range Counting and Reporting
• 10.50-11.10: Mark de Berg, Prosenjit Bose and Leonidas Theocharous. On the Doubling Dimension and the Perimeter of Geodesically Convex Sets in Fat Polygons
• 11.10-11.30: Anna Brötzner, Bengt J. Nilsson and Christiane Schmidt. Improved Approximation of Two Watchmen's Routes in Simple Polygons
• 11.30-11.40: Break
• 11.40-12.00: Nicole Funk, Annika Hennes, Johanna Hillebrand and Sarah Sturm. Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means
• 12.00-12.20: Édouard Bonnet, Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk and Paweł Rzążewski. QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
• 12.20-12.40: Anand Louis and Kirtan Vora. Semirandom Planted Bipartite Subgraphs

Back to table

SF3

• 13.40-14.00: Divya Bajaj, Bin Fu, Ryan Knobel, Austin Luchsinger, Aiden Massie, Pablo Santos, Ramiro Santos, Robert Schweller, Evan Tomai and Tim Wylie. Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks
• 14.00-14.20: Michael A. Bekos, Eleni Katsanou, Philipp Kindermann and Maria Eleni Pavlidi. How Many Slopes Does Polynomial Area Cost?
• 14.20-14.40: Nicolas Bousquet, Frank Connor, Remy El Sabeh, Louis-Roy Langevin, Amer E. Mouawad, Naomi Nishimura and Agnes Totschnig. Robotic arm rotation: Standing up is harder than you think
• 14.40-15.00: Dušan Knop, Nikolaos Melissinos and Manolis Vasilakis. Parameterized Critical Node Cut Revisited

Back to table

SF4

• 15.30-15.50: Manoj Gupta, Shahbaz Khan and Madhu Surendra. Dynamic MIS Revisited: Incremental, Fault Tolerant and Fully Dynamic (recorded talk)
• 15.50-16.10: Anastasiia Tkachenko and Haitao Wang. Maximum Independent Sets in Disk Graphs with Disks in Convex Position (recorded talk)
• 16.10-16.30: Tatsuya Terao. Faster Approximate Linear Matroid Intersection (recorded talk) (best student-paper award)

Back to table