WADS 2017 Schedule

All talks are in the Arts and Administration building . Enter through the glass doors #14, east side of the building. The main conference room is A-1043, immediately to the right from the entrance. Talks in sessions 1B to 7B are in room A-1046 (further down the hall from A-1043, in front of the Tim Hortons coffee stand ).

Sunday, July 30
7:30pm Reception at Get Stuffed, 190 Duckworth St.
Monday, July 31
9:30-10:30 Fine-Grained Complexity of Problems in P, Virginia Vassilevska Williams
10:30-10:50 Coffee break
10:50-11:15 Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron, Nadia Benbernou, Erik D. Demaine, Martin L. Demaine and Anna Lubiw
11:20-12:10 Session 1A (Chair: Ian Munro) Session 1B (Chair: Erik Demaine)
Dynamic Graph Coloring,  Luis Barba, Jean Cardinal, Matias Korman, Stefan Langerman, André van Renssen, Marcel Roeloffzen and Sander Verdonschot Split Packing: Packing Circles into Triangles with Optimal Worst-Case Density, Sándor Fekete, Sebastian Morr and Christian Scheffer 
Approximating Small Balanced Vertex Separators in Almost Linear Time,  Sebastian Brandt and Roger Wattenhofer Capacitated Center Problems with Two-Sided Bounds and Outliers, Hu Ding, Lunjia Hu, Huang Lingxiao and Jian Li 
12:05-14:00 Lunch
14:00-15:40 Session 2A (Chair: Faith Ellen) Session 2B (Chair: Antonina Kolokolova)
Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs, Erik Demaine and Quanquan Liu  Parameterized Complexity of Geometric Covering Problems Having Conflicts, Aritra Banik, Fahad Panolan, Venkatesh Raman, Vibha Sahlot and Saket Saurabh 
Conditional Lower Bounds for Space/Time Tradeoffs, Isaac B. Goldstein, Tsvi Kopelowitz, Moshe Lewenstein and Ely Porat A Polynomial Kernel for Distance-Hereditary Vertex Deletion, Eun Jung Kim and O-Joung Kwon 
Optimal Query Time for Encoding Range Majority, Pawel Gawrychowski and Patrick K. Nicholson  The Complexity of Tree Partitioning, Zhao An, Qilong Feng, Iyad Kanj and Ge Xia 
Fast and Compact Planar Embeddings, Leo Ferres, José Fuentes, Travis Gagie, Meng He and Gonzalo Navarro  When can Graph Hyperbolicity be Computed in Linear Time? Till Fluschnik, Christian Komusiewicz, George Mertzios, André Nichterlein, Rolf Niedermeier and Nimrod Talmon 
15:40-16:00 Coffee break
16:00-17:40 Session 3A (Chair: Travis Gagie) Session 3B (Chair: Virginia Vassilevska Williams)
Relaxing the Irrevocability Requirement for Online Graph Algorithms, Joan Boyar, Lene Favrholdt, Michal Kotrbcik and Kim S. Larsen Improved distance sensitivity oracles via tree partitioning, Ran Duan and Tianyi Zhang 
A Deterministic Algorithm for Online Steiner Tree Leasing, Marcin Bienkowski, Artur Kraska and Paweł Schmidt  δ-Greedy t-spanner, Gali Bar-On and Paz Carmi
Busy-Time Scheduling on a Bounded Number of Machines, Frederic Koehler and Samir Khuller  Local Routing in Spanners Based on WSPDs, Prosenjit Bose, Jean-Lou De Carufel, Vida Dujmović and Frédérik Paradis 
An EPTAS for Scheduling on Unrelated Machines of Few Different Types, Klaus Jansen and Marten Maack Faster Randomized Worst-Case Update Time for Dynamic Subgraph Connectivity, Ran Duan and Le Zhang
18:00-19:00 Business meeting
Tuesday, August 1
9:30-10:30 How efficiently can easy dynamic programs be approximated? Michael Saks
10:30-10:50 Coffee break
10:50-12:30 Session 4A (Chair: Kim Larsen) Session 4B (Chair: Therese Biedl)
Delta-Fast Tries: Local Searches in Bounded Universes with Linear Space, Marcel Ehrhardt and Wolfgang Mulzer  Algorithms for Covering Multiple Barriers, Shimin Li and Haitao Wang 
How to Play Hot and Cold on a Line,  Herman Haverkort, David Kübel, Elmar Langetepe and Barbara Schwarzwald Balanced Line Separators of Unit Disk Graphs, Paz Carmi, Man Kwun Chiu, Matthew Katz, Matias Korman, Yoshio Okamoto, André van Renssen, Marcel Roeloffzen, Taichi Shiitada and Shakhar Smorodinsky 
Improved Average Complexity for Comparison-Based Sorting, Kazuo Iwama and Junichi Teruyama  Covering Segments with Unit Squares, Ankush Acharyya, Subhas C. Nandy 
The I/O Complexity of Strassen’s Matrix Multiplication with Recomputation, Gianfranco Bilardi and Lorenzo De Stefani  The Homogeneous Broadcast Problem in Narrow and Wide Strips, Mark de Berg, Hans L. Bodlaender and Sándor Kisfaludi-Bak
12:30-15:00 Lunch
15:00-22:00 Excursion and dinner (boat tour followed by a beach BBQ) . Bus pick-up at 3:30pm, at a downtown and a campus locations.
  • Downtown: Sheraton Hotel Newfoundland (115 Cavendish square), parking lot.
  • Campus: In front of the building where talks are (Arts and Administration), entrance facing south-east (towards Elizabeth st).
If either one works for you, please come to the downtown location. The buses should be yellow with CityWide written on them.
Wednesday, August 2
9:30-10:30 Algorithms for Geometric Similarity: Recent Developments, Pankaj Agarwal
10:30-10:50 Coffee break
10:50-12:05 Session 5A (Chair: Michael Saks) Session 5B (Chair: Pankaj Agarwal)
Fast Exact Algorithms for Survivable Network Design with Uniform Requirements, Akanksha Agrawal, Pranabendu Misra, Fahad Panolan and Saket Saurabh A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings, Therese Biedl and Philippe Demontigny 
Posimodular Function Optimization, Magnus M. Halldorsson, Toshimasa Ishii, Kazuhisa Makino and Kenjiro Takazawa  Obedient Plane Drawings for Disk Intersection Graphs, Bahareh Banyassady, Michael Hoffmann, Boris Klemz, Maarten Löffler and Tillmann Miltzow
Faster Algorithm for Truth Discovery via Range Cover, Ziyun Huang, Hu Ding and Jinhui Xu  The Complexity of Drawing Graphs on Few Lines and Few Planes, Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbitsky and Alexander Wolff 
12:05-14:00 Lunch
14:00-15:40 Session 6A (Chair: Yoshio Okamoto) Session 6B (Chair: Bengt J. Nilsson)
Covering Uncertain Points in a Tree, Haitao Wang and Jingru Zhang  Searching edges in the overlap of two plane graphs, John Iacono, Elena Khramtcova and Stefan Langerman 
Replica Placement on Bounded Treewidth Graphs, Anshul Aggarwal, Venkatesan Chakaravarthy, Neelima Gupta, Yogish Sabharwal, Sachin Sharma and Sonika Thakral Maximum Plane Trees in Multipartite Geometric Graphs, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Kimberly Crosbie, David Eppstein, Anil Maheshwari and Michiel Smid  
An Optimal XP Algorithm for Hamiltonian Cycle on Graphs of Bounded Clique-width, Benjamin Bergougnoux, Mamadou Moustapha Kanté and O-Joung Kwon  Minimizing the Continuous Diameter when Augmenting a Tree with a Shortcut, Jean-Lou De Carufel, Carsten Grimm, Michiel Smid and Stefan Schirra  
Splitting $B_2$-VPG Graphs into Outer-string and Co-comparability Graphs, Therese Biedl and Martin Derka  All-Pairs Shortest Paths in Geometric Intersection Graphs, Timothy Chan and Dimitrios Skrepetos
15:40-16:00 Coffee break
16:00-17:40 Session 7A (Chair: Joan Boyar) Session 7B (Chair: Meng He)
Improved Algorithms for Computing k-Sink on Dynamic Flow Path Networks,  Binay Bhattacharya, Mordecai J. Golin, Yuya Higashikawa, Tsunehiko Kameda and Naoki Katoh  Effectiveness of Local Search for Art Gallery Problems, Sayan Bandyapadhyay and Aniket Basu Roy
An Improved Algorithm for Diameter-Optimally Augmenting Paths in a Metric Space, Haitao Wang  Stochastic Closest-pair Problem and Most-likely Nearest-neighbor Search in Tree Spaces, Jie Xue and Yuan Li 
Modular Circulation and Applications to Traffic Management, Philip Dasler and David Mount  On the expected diameter, width, and complexity of a stochastic convex-hull, Jie Xue, Yuan Li and Ravi Janardan