ISAAC 2020 Program
Proceedings Day 1 Day 2 Day 3 Day 4 Day 5All in Hong Kong time (UTC+8)
December 14 (Monday)
15:50–16:00 Opening(Chair: Siu-Wing Cheng)
16:00–17:00 INVITED TALK 1 (Chair: Yixin Cao)
Sang-il Oum
How to decompose a graph into a tree-like structure
17:00–17:10 BREAK
17:10–18:10 SESSION 1 (Chair: Sang-il Oum)
Joachim Gudmundsson, Yuan Sha, and Sampson Wong
Approximating the packedness of polygonal curves
Marc van Kreveld, Tillmann Miltzow, Tim Ophelders, Willem Sonke, and Jordi L. Vermeulen
Between Shapes, Using the Hausdorff Distance
Boris Aronov and Jean Cardinal
Geometric Pattern Matching Reduces to k-SUM
18:10–19:40 BREAK
19:40–20:50 SESSION 2 (Chair: Minming Li)
Wolfgang Mulzer and Max Willert
Compact Routing in Unit Disk Graphs
Maciej Dulęba, Paweł Gawrychowski, and Wojciech Janczewski
Efficient Labeling for Reachability in Directed Acyclic Graphs
Bartlomiej Dudek and Pawel Gawrychowski
Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs (Best paper, 30 mins)
20:50–21:00 BREAK
21:00–22:00 SESSION 3 (Chair: Jesper Jansson)
Anadi Agrawal and Paweł Gawrychowski
A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem
Anthony Labarre
Sorting by Prefix Block-Interchanges
Philip Bille and Inge Li Gørtz
Random Access in Persistent Strings
December 15 (Tuesday)
8:00–9:20 SESSION 4 (Chair: Kyle Fox)
Peter Bradshaw, Tomáš Masařík, and Ladislav Stacho
Flexible List Colorings in Graphs with Special Degeneracy Conditions
Adrian Dumitrescu, Anirban Ghosh, and Csaba D. Tóth
Sparse Hop Spanners for Unit Disk Graphs
Haozhou Pang and Mohammad R. Salavatipour
Approximation Algorithms for Generalized Path Scheduling
Dylan Hyatt-Denesik, Mirmahdi Rahgoshay, and Mohammad R. Salavatipour
Approximations for Throughput Maximization
9:20–9:40 BREAK
9:40–11:00 SESSION 5 (Chair: Richard Peng)
Eunjin Oh
Shortest-Path Queries in Geometric Networks
Takao Asano and Hiroyuki Umeda
Cake Cutting: An Envy-free and Truthful Mechanism with a Small Number of Cuts
Jungho Ahn, Eun Jung Kim, and Euiwoong Lee
Towards constant-factor approximation for chordal / distance-hereditary vertex deletion
Kristóf Bérczi, Naonori Kakimura, and Yusuke Kobayashi
Market Pricing for Matroid Rank Valuations
16:00–17:00 INVITED TALK 2(Chair: Siu-Wing Cheng)
Ke Yi
Worst-case optimal join algorithms
17:00–17:10 BREAK
17:10–18:10 SESSION 6 (Chair: Ke Yi)
Kentaro Sumigawa, Sankardeep Chakraborty, Kunihiko Sadakane, and Srinivasa Rao Satti
Enumerating Range Modes
Guido Brückner and Ignaz Rutter
An SPQR-Tree-Like Embedding Representation for Level Planarity
Stefan Funke and Felix Weitbrecht
Efficiently Computing all Delaunay Triangles Occurring over all Contiguous Subsequences
18:10–19:40 BREAK
19:40–20:50 SESSION 7 (Chair: Minming Li)
Richard Santiago and Yuichi Yoshida
Weakly Submodular Function Maximization Using Local Submodularity Ratio
Umang Bhaskar and Gunjan Kumar
Partial Function Extension with Applications to Learning and Property Testing
Joep Hamersma, Marc van Kreveld, Yushi Uno, and Tom C. van der Zanden
Gourds: a sliding-block puzzle with turning (Best paper, 30 mins)
20:50–21:00 BREAK
21:00–22:00 SESSION 8 (Chair: Ryuhei Uehara)
Nicolas Bousquet, Alice Joffard, and Paul Ouvrard
Linear transformations between dominating sets in the TAR-model
Till Fluschnik, Rolf Niedermeier, Carsten Schubert, and Philipp Zschoche
Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs
Matthias Bentert, Klaus Heeger, and Dušan Knop
Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters
December 16 (Wednesday)
8:00–9:20 SESSION 9 (Chair: Guochuan Zhang)
Josh Brunner, Erik D. Demaine, Dylan Hendrickson, and Julian Wellman
Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard
Erik D. Demaine, Justin Kopinsky, and Jayson Lynch
Recursed is not Recursive: A Jarring Result
Leo Alcock, Sualeh Asif, Jeffrey Bosboom, Josh Brunner, Charlotte Chen, Erik D. Demaine, Rogers Epstein, Adam Hesterberg, Lior Hirschfeld, William Hu, Jayson Lynch, Sarah Scheffler, and Lillian Zhang
Arithmetic Expression Construction
Ke Chen and Adrian Dumitrescu
Multiparty Selection
9:20–9:40 BREAK
9:40–11:00 SESSION 10 (Chair: Qilong Feng)
Kei Uchizawa
Size, Depth and Energy of Threshold Circuits Computing Parity Function
Yoshifumi Sakai and Shunsuke Inenaga
A reduction of the dynamic time warping distance to the longest increasing subsequence length
Yuma Tamura, Takehiro Ito, and Xiao Zhou
Minimization and Parameterized Variants of Vertex Partition Problems on Graphs
Sanjana Dey, Florent Foucaud, Subhas C. Nandy, and Arunabha Sen
Discriminating Codes in Geometric Setups
16:00–17:00 SESSION 11 (Chair: Sungjin Im)
Predrag Krnetić, Darya Melnyk, Yuyi Wang, and Roger Wattenhofer
The k-Server Problem with Delays on the Uniform Metric Space
Mark de Berg, Aleksandar Markovic, and Seeun William Umboh
The Online Broadcast Range-Assignment Problem
Nguyễn Kim Thắng
Online Primal-Dual Algorithms with Configuration Linear Programs
17:00–19:40 BREAK
19:40–20:40 SESSION 12 (Chair: László Végh)
Loukas Georgiadis and Evangelos Kosinas
Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems
Kishen N. Gowda, Aditya Lonkar, Fahad Panolan, Vraj Patel, and Saket Saurabh
Improved FPT Algorithms for Deletion to Forest-like Structures
Tomohiro Koana, Christian Komusiewicz, and Frank Sommer
Computing Dense and Sparse Subgraphs of Weakly Closed Graphs
20:40–21:00 BREAK
21:00–22:00 SESSION 13 (Chair: Prudence Wong)
Taku Onodera and Tetsuo Shibuya
Wear Leveling Revisited
Trung Thanh Nguyen and Jörg Rothe
Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs
Martin Koutecký and Johannes Zink
Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines
December 17 (Thursday)
8:00–9:20 SESSION 14 (Chair: Kirk Pruhs)
Pedro Montealegre, Diego Ramírez-Romero, and Ivan Rapaport
Shared vs Private Randomness in Distributed Interactive Proofs
Xuangui Huang
Space Hardness of Solving Structured Linear Systems
Angel A. Cantu, Austin Luchsinger, Robert Schweller, and Tim Wylie
Signal Passing Self-Assembly Simulates Tile Automata
Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang, and Chunhao Wang
Quantum-inspired algorithms for solving low-rank linear equation systems with logarithmic dependence on the dimension
9:20–10:00 BREAK
10:00–10:40 SESSION 15 (Chair: Yoshio Okamoto)
Kangsan Kim, Yongho Shin, and Hyung-Chan An
Constant-Factor Approximation Algorithms for the Parity-Constrained Facility Location Problem
Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu, and Jianxin Wang
A Unified Framework of FPT Approximation Algorithms for Clustering Problems
10:40–19:40 BREAK
19:40–20:40 SESSION 16 (Chair: Magnus Wahlström)
Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, and Amer E. Mouawad
On girth and the parameterized complexity of token sliding and token jumping
Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse, and Paweł Rzążewski
Sparsification Lower Bounds for List H-Coloring
Fabian Frei, Edith Hemaspaandra, and Jörg Rothe
Complexity of Stability
20:40–21:00 BREAK
21:00–22:00 SESSION 17 (Chair: Michał Pilipczuk)
Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, and Philipp Zschoche
Finding Temporal Paths under Waiting Time Constraints
Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, and Manuel Sorge
The Complexity of Connectivity Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, and Nikolaos Melissinos
(In)approximability of Maximum Minimal FVS
December 18 (Friday)
15:00–16:20 SESSION 18 (Chair: Wing-Kai Hon)
William L. Holland, Anthony Wirth, and Justin Zobel
Recency queries with succinct representation
Meng He, J. Ian Munro, Yakov Nekrich, Sebastian Wild, and Kaiyu Wu
Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees
Amihood Amir and Itai Boneh
Update Query Time Trade-off for Dynamic Suffix Arrays
Sung-Hwan Kim and Hwan-Gue Cho
Indexing Isodirectional Pointer Sequences
16:20–16:40 BREAK
16:40–18:00 SESSION 19 (Chair: O-Joung Kwon)
Walter Kern and Daniël Paulusma
Contracting to a Longest Path in H-Free Graphs
Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, and Danil Sagunov
Diverse Pairs of Matchings
Dibyayan Chakraborty, Sandip Das, Florent Foucaud, Harmender Gahlawat, Dimitri Lajou, and Bodhayan Roy
Algorithms and complexity for geodetic sets on planar and chordal graphs
Nikhil Kumar
Multicommodity Flows in Planar Graphs with Demands on Faces