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. | |
| ||
| ||
| 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 | |
