Conference Program

Sunday, June 17
19:00 Welcome Reception
Join us for registration, drinks and snacks at one of the best bars in Malmö, Care Of, at Fiskehamnsgatan 11, in the Malmö Live block, very close to the University building where the conference takes place. (Don't get confused by the Google streetview picture: the building wasn't there when it was taken!)

All talks are in room NI:C0E11, ground floor of the Niagara building, Nordenskiöldsgatan 1, Malmö

Click on invited talk title to view abstract.

Monday, June 18
8:15 - 8:55 Registration
8:55 - 9:00 Welcome Address
9:00 - 9:50 Invited Talk: Sorelle Friedler. Optimizing Society? Ensuring Fairness in Automated Decision-Making. Session chair: Bengt J. Nilsson
9:50 - 10:10 Coffee Break
Session 1: Graphs Session chair: Therese Biedl
10:10 - 10:35 Fedor Fomin, Petr Golovach, Torstein Strømme and Dimitrios Thilikos. Partial Complementation of Graphs
10:35 - 11:00 Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang and Tianyi Zhang. An Improved Algorithm for Incremental DFS Tree in Undirected Graphs
11:00 - 11:25 Takehiro Ito and Yota Otachi. Reconfiguration of Colorable Sets in Classes of Perfect Graphs
11:25 - 11:50 Diptarka Chakraborty and Debarati Das. Sparse Weight Tolerant Subgraph for Single Source Shortest Path
11:50 - 13:15 Lunch (Niagara Restaurant)
13:15 - 13:40 Industry talk with Apptus Technologies Mikael Hammar. Exposure Strategies in e-Commerce
Session 2: Matrices and Optimization Session chair: Petteri Kaski
13:40 - 14:05 Khaled Elbassioni and Kazuhisa Makino. Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices
14:05 - 14:30 Lingxiao Huang, Yifei Jin and Jian Li. SVM via Saddle Point Optimization: New Bounds and Distributed Algorithms (CLICK FOR SLIDES!)
14:30 - 14:55 Sutanu Gayen and Vinodchandran Variyam. New Algorithms for Distributed Sliding Windows
14:55 - 15:20 Coffee Break
Session 3: Computational Geometry Session chair: Mikael Hammar
15:20 - 15:45 Ahmed Abdelkader and David Mount. Economical Delone Sets for Approximating Convex Bodies
15:45 - 16:10 Therese Biedl, Ahmad Biniaz and Martin Derka. On the Size of Outer-String Representations
16:10 - 16:35 Prosenjit Bose, Paz Carmi, J. Mark Keil, Saeed Mehrabi and Debajyoti Mondal. Boundary Labeling for Rectangular Diagrams
16:35 - 17:00 Omrit Filtser and Matthew Katz. Algorithms for the Discrete Frechet Distance under Translation
Tuesday, June 19
8:30 - 9:00 Registration
9:00 - 9:50 Invited Talk: Nancy M. Amato. Sampling-Based Motion Planning: From Intelligent CAD to Crowd Simulation to Protein Folding. Session chair: David Eppstein
9:50 - 10:10 Coffee Break
Session 4: Visibility, Motion and Paths Session chair: Erik Krohn
10:10 - 10:35 Prosenjit Bose, Sander Verdonschot, Ahmad Biniaz and Aurelien Ooms. Improved Bounds for Guarding Plane Graphs with Edges
10:35 - 11:00 Prosenjit Bose and Thomas Shermer. Gathering by Repulsion
11:00 - 11:25 Hee-Kap Ahn, Eunjin Oh, Lena Schlipf, Fabian Stehn and Darren Strash. On Romeo and Juliet Problems: Minimizing Distance-to-Sight
11:25 - 11:50 Pankaj Agarwal, Neeraj Kumar, Stavros Sintos and Subhash Suri. Computing Shortest Paths in the Plane with Removable Obstacles
11:50 - 13:15 Lunch (Niagara Restaurant)
Session 5: Data Structures Session chair: Jesper Larsson
13:15 - 13:40 Michael Mitzenmacher, Konstantinos Panagiotou and Stefan Walzer. Load Thresholds for Cuckoo Hashing with Double Hashing
13:40 - 14:05 Yuancheng Yu, Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams and Yinzhan Xu. Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures
14:05 - 14:30 Hicham El-Zein, Ian Munro and Yakov Nekrich. Succinct Dynamic One-Dimensional Point Reporting
14:30 - 14:55 Business Meeting
14:55 - 15:20 Coffee Break
15:20 - 17:30 Social Event
19:00 - Conference Dinner
Wednesday, June 20
8:30 - 9:00 Registration
9:00 - 9:50 Invited Talk: Ankur Moitra. Robustness Meets Algorithms. Session chair: Joan Boyar
9:50 - 10:10 Coffee Break
Session 6: Graphs and Trees Session chair: Kim Skak Larsen
10:10 - 10:35 Evripidis Bampis, Bruno Escoffier, Michael Lampis and Vangelis Paschos. Multistage Matchings
10:35 - 11:00 Alexander Pilz. Planar 3-SAT with a Clause/Variable Cycle
11:00 - 11:25 Mikhail Rudoy and Erik Demaine. Tree-Residue Vertex-Breaking: a New Tool for Proving Hardness
11:25 - 11:50 Matthias Bentert, Josef Malík and Mathias Weller. Tree Containment With Soft Polytomies
11:50 - 13:15 Lunch (Niagara Restaurant)
Session 7: Computational Geometry Session chair: Prosenjit Bose
13:15 - 13:40 Kim Thang Nguyen. A Greedy Algorithm for Subspace Approximation
13:40 - 14:05 Ahmad Biniaz, Anil Maheshwari and Michiel Smid. Flip Distance to some Plane Configurations
14:05 - 14:30 Luis Barba, Michael Hoffmann, Matias Korman and Alexander Pilz. Convex Hulls in Polygonal Domains
14:30 - 14:55 Shang-En Huang and Seth Pettie. Lower Bounds on Sparse Spanners, Emulators, and Diameter-Reducing Shortcuts
14:55 - 15:20 Coffee Break
Session 8: Graphs Session chair: Pawel Zylinski
15:20 - 15:45 Petr Golovach, Pinar Heggernes, Athanasios Konstantinidis, Paloma Lima and Charis Papadopoulos. Parameterized Aspects of Strong Subgraph Closure
15:45 - 16:10 Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi and Florian Sikora. Parameterized Orientable Deletion
16:10 - 16:35 Andreas Emil Feldmann and Dániel Marx. The Parameterized Hardness of the k-Center Problem in Transportation Networks
16:35 - 17:00 Lukasz Kowalik and Arkadiusz Socala. Tight Lower Bounds for List Edge Coloring
17:00 Conference Ends

Abstracts of Invited Talks

Optimizing Society? Ensuring Fairness in Automated Decision-Making

Sorelle Friedler
Department of Computer Science, Haverford College

Algorithms are increasingly used to make high-stakes decisions about people; who goes to jail, what neighborhoods police deploy to, and who should be hired for a job. But if we want these decisions to be fair, this means we must take societal notions of fairness and express them using the language of math. What is a fair decision and how can it be guaranteed?
In this talk, we’ll discuss recent work from the new and growing field of Fairness, Accountability, and Transparency. We will examine technical definitions of fairness and non-discrimination that have been proposed and their societal counterparts. We’ll also discuss methods for ensuring that algorithms are making decisions as desired, from methods to audit black-box algorithms to white-box interpretability techniques. This important field necessitates societally informed and mathematically rigorous work; we’ll discuss open problems in this light.

Sampling-Based Motion Planning: From Intelligent CAD to Crowd Simulation to Protein Folding

Nancy M. Amato
Department of Computer Science and Engineering, Texas A&M University

Motion planning has application in robotics, animation, virtual prototyping and training, and even for seemingly unrelated tasks such as evaluating architectural plans or simulating protein folding. Surprisingly, sampling-based planning methods have proven effective on problems from all these domains. In this talk, we provide an overview of sampling-based planning and describe some variants developed in our group, including strategies suited for manipulation planning and for user interaction. For virtual prototyping, we show that in some cases a hybrid system incorporating both an automatic planner and haptic user input leads to superior results. For crowd simulation, we describe techniques for evacuation planning and for evaluating architectural designs. Finally, we describe our application of sampling-based motion planners to simulate molecular motions, such as protein and RNA folding.

Robustness Meets Algorithms

Ankur Moitra
Department of Mathematics, Massachusetts Institute of Technology

In every corner of machine learning and statistics, there is a need for estimators that work not just in an idealized model but even when their assumptions are violated. Unfortunately in high-dimensions, being provably robust and efficiently computable are often at odds with each other. In this talk, we give the first efficient algorithm for estimating the parameters of a high-dimensional Gaussian which is able to tolerate a constant fraction of corruptions that is independent of the dimension. Prior to our work, all known estimators either needed time exponential in the dimension to compute, or could tolerate only an inverse polynomial fraction of corruptions. Not only does our algorithm bridge the gap between robustness and algorithms, it turns out to be highly practical in a variety of settings.