ISAAC 2019 Program

Sunday Dec. 8

09:00-20:00

Registration

Location: 1F @ Howard Johnson Hotel

Monday Dec. 9

08:30-09:00

Registration                               Location: 1F @ New Research Building

09:00-10:00

Keynote Speech: Approximating the Independence Polynomial Leslie Ann Goldberg (University of Oxford, UK)

10:00-10:10

Group Photo

10:10-10:30

Coffee/Tea Break

Session 1A: Complexity

Session 1B: Geometry

10:30-10:50

On the Hardness of Set Disjointness and Set Intersection with Bounded Universe (Isaac B. Goldstein, Moshe Lewenstein and Ely Porat)

Approximate Euclidean shortest paths in polygonal domains (R Inkulu and Sanjiv Kapoor)

10:50-11:10

The I/O complexity of hybrid algorithms for square (Lorenzo De Stefani)

Minimum-Width Double-Strip and Parallelogram Annulus (Sang Won Bae)

11:10-11:30

Complexity of Linear Operators (Alexander Kulikov, Ivan Mikhailin, Andrey Mokhov and Vladimir Podolskii)

The $k$-Fréchet distance: How to walk your dog while teleporting(Hugo A. Akitaya, Maike Buchin, Leonie Ryvkin and Jérôme )

11:30-11:50

On the Complexity of Lattice Puzzles (Yasuaki Kobayashi, Koki Suetsugu, Hideki Tsuiki and Ryuhei Uehara)

Distance Measures for Embedded Graphs (Hugo A. Akitaya, Maike Buchin, Bernhard Kilgus, Stef Sijben and Carola Wenk)

11:50-13:20

Lunch

Session 2A: Estimation and Enumeration

Session 2B: Data Structure

13:20-13:40

Lower Bound for Non-Adaptive Estimation of the Number of Defective Items (Nader Bshouty)

External Memory Planar Point Location with Fast Updates (John Iacono, Ben Karsin and Grigorios Koumoutsos)

13:40-14:00

Triangle Estimation using Tripartite Independent Set Queries (Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh and Gopinath Mishra)

On Approximate Range Mode and Range Selection (Hicham El-Zein, Meng He, Ian Munro, Yakov Nekrich and Bryce Sandlund)

14:00-14:20

A Polynomial-delay Algorithm for Enumerating (Kazuya Haraguchi and Hiroshi Nagamochi)

On Optimal Balance in B-trees: What Does it Cost to Stay (Rolf Fagerberg, David Hammer and Ulrich Meyer)

14:20-14:40

Coffee/Tea Break

Session 3A: Graph Algorithms

Session 3B: Approximation Algorithms

14:40-15:00

Graph Searches and Their End Vertices (Yixin Cao, Guozhen Rong, Jianxin Wang and Zhifeng Wang)

Approximating the Geometric Edit Distance (Kyle Fox and Xinyi Li)

15:00-15:20

Two Phase Transitions in Two-way Bootstrap Percolation (Ahad N. Zehmakan)

Small Candidate Set for Translational Pattern Search (Ziyun Huang, Qilong Feng, Jianxin Wang and Jinhui Xu)

15:20-15:40

Reachability in High Treewidth Graphs (Rahul Jain and Raghunath Tewari)

A 21/16-approximation for the minimum 3-path partition problem (Yong Chen, Randy Goebel, Bing Su, Weitian Tong, Yao Xu and An Zhang)

15:40-16:00

Cyclability in Graph Classes (Christophe Crespelle, Carl Feghali and Petr Golovach)

New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs (Nil Mamano, Alon Efrat, David Eppstein, Daniel Frishberg, Michael Goodrich, Stephen Kobourov, Pedro Matias and Valentin Polishchuk)

Tuesday Dec. 10

08:30-09:00

Registration

09:00-10:00

Keynote Speech: Beyond trace reconstruction: Population recovery from the deletion channel Xi Chen (Columbia University, USA)

10:00-10:20

Coffee/Tea Break

Session 4A: Data Structure

Session 4B: Geometry

10:20-10:40

An improved data structure for left-right maximal generic words problem (Yuta Fujishige, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda)

Unbounded Regions of High-Order Voronoi Diagrams of Lines and Segments in Higher Dimensions (Gill Barequet, Evanthia Papadopoulou and Martin Suderland)

10:40-11:00

Top Tree Compression of Tries (Philip Bille, Pawel Gawrychowski, Inge Li Gørtz, Gad M.Landau )

How does object fatness impact the complexity of packing in d dimensions? (Sándor Kisfaludi-Bak, Dániel Marx and Tom van der Zanden)

11:00-11:20

Path and Ancestor Queries over Trees with Multidimensional Weight Vectors (Meng He and Serikzhan Kazi)

Local Routing in Sparse and Lightweight Geometric Graphs (Vikrant Ashvinkumar, Joachim Gudmundsson, Christos Levcopoulos, Bengt Nilsson and André van Renssen)

11:20-11:40

Internal Dictionary Matching (Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Modamed, Jakub Radoszewski, Wojciech Rytter and Tomasz Walen)

The Weighted k-center Problem in Trees for Fixed k (Binay Bhattacharya, Sandip Das and Subhadeep Dev)

11:40-13:20

Lunch

Session 5A: Graph Algorithms

Session 5B: Combinatorial Problems

13:20-13:40

The Generalized Microscopic Image Reconstruction Problem (Amotz Bar-Noy, Toni Böhnlein, Zvi Lotker, David Peleg and Dror Rawitz)

Efficient Interactive Proofs for Linear Algebra (Chris Hickey and Graham Cormode)

13:40-14:00

Stabilization Time in Minority Processes (Pál András Papp and Roger Wattenhofer)

Sliding window property testing for regular languages (Moses Ganardi, Danny Hucke, Markus Lohrey and Tatiana Starikovskaya)

14:00-14:20

Efficiently Realizing Interval Sequences (Amotz Bar-Noy, Keerti Choudhary, David Peleg and Dror Rawitz)

Result-Sensitive Fault-Tolerant Binary Search (Narthana Epa, Junhao Gan and Anthony Wirth)

14:20-14:40

Local cliques in ER-perturbed random geometric graphs (Matthew Kahle, Minghao Tian and Yusu Wang)

Searching for Cryptogenography Upper Bounds via Sum (Dominik Scheder, Shuyang Tang and Jiaheng Zhang)

14:40-15:00

Coffee/Tea Break

Session 6A: Distributed Algorithms

Session 6B: Online Algorithms

15:00-15:20

Gathering and Election by Mobile Robots in a Continuous Cycle (Ryan Killick, Evangelos Kranakis, Paola Flocchini, Nicola Santoro and Masafumi Yamashita)

Online Knapsack Problems with a Resource Buffer (Xin Han, Yasushi Kawase, Kazuhisa Makino and Haruki Yokomaku)

15:20-15:40

Step-by-Step Community Detection in Volume-Regular Graphs (Luca Becchetti, Emilio Cruciani, Francesco Pasquale and Sara Rizzo)

Online Algorithms for Warehouse Management (Philip Dasler and David Mount)

15:40-16:00

Accurate MapReduce Algorithms for k-median and k-means in General Metric Spaces (Alessio Mazzetto, Andrea Pietracaprina and Geppino Pucci)

A Competitive Algorithm for Random-Order Stochastic Virtual Circuit Routing (Kim Thang Nguyen)

16:00-16:20

Efficient Circuit Simulation in MapReduce (Fabian Frei and Koichi Wada)

Concurrent Distributed Serving with Mobile Servers (Abdolhamid Ghodselahi, Fabian Kuhn and Volker Turau)

16:20-16:40

Coffee/Tea Break

Session 7A: Algorithmic Game Theory

Session 7B: Minor-free Graph Algorithms

16:40-17:00

Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists (Koki Hamada, Shuichi Miyazaki and Hiroki Yanagisawa)

Blocking dominating sets for H-free graphs via edge contractions (Esther Galby, Paloma de Lima and Bernard Ries)

17:00-17:20

Approximate Pricing in Networks: How to Boost the Betweenness and Revenue of a Node (Ruben Brokkelkamp, Sven Polak, Guido Schäfer and Yllka Velaj)

Tracking Paths in Planar Graphs (David Eppstein, Michael T. Goodrich, James A. Liu and Pedro A. Matias)

17:20-17:40

On One-Round Discrete Voronoi Games (Mark de Berg, Sándor Kisfaludi-Bak and Mehran Mehr)

Neighborhood inclusions for minimal dominating sets enumeration: linear and polynomial delay algorithms in P7-free and P8-free chordal graphs (Oscar Defrain and Lhouari Nourine)

18:30-20:30

Banquet Dinner

Wednesday Dec. 11

08:30-09:00

Registration

09:00-10:00

Keynote Speech: Influence Maximization: Pushing the Limits of Combinatorial Optimizations and Online Learning Wei Chen (Microsoft Research Asia)

10:10-10:30

Coffee/Tea Break

Session 8A: Approximation Algorithms

Session 8B: Parameterized Complexity

10:30-10:50

On Adaptivity Gaps of Influence Maximization under the Independent Cascade Model (Wei Chen and Binghui Peng)

On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials (V. Arvind, Abhranil Chatterjee, Rajit Datta and Partha Mukhopadhyay)

10:50-11:10

Dual-mode greedy algorithms can save energy (Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, Paolo Penna and Guido Proietti)

Parameterized Dichotomy of Deletion to List Matrix-Partition for low-order Matrices (Akanksha Agrawal, Sudeshna Kolay, Jayakrishnan Madathil and Saket Saurabh)

11:10-11:30

Improved Algorithms for Clustering with Outliers (Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu and Jianxin Wang)

Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists (Robert Bredereck, Klaus Heeger, Dušan Knop and Rolf Niedermeier)

11:30-11:0

Coffee/Tea Break

Session 9A: Online Algorithms

Session 9B: FPT and Exact Algorithms

11:30-11:50

New Results for the k-Secretary Problem (Susanne Albers and Leon Ladewig)

Minimizing and Computing the Inverse Geodesic Length on Trees (Serge Gaspers and Joshua Lau)

11:50-12:10

Online Multidimensional Packing Problems in the Random-Order Model (David Naori and Danny Raz)

When Maximum Stable can be solved in FPT time (Nicolas Bousquet, Edouard Bonnet, Rémi Watrigant and Stéphan Thomassé)

12:10-12:30

Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics (Marcin Bienkowski, Łukasz Jeż and Paweł Schmidt)

Measure and Conquer for Max Hamming Distance XSAT (Gordon Hoi and Frank Stephan)

12:30-14:00

Lunch