December 16 (Tue)

Room A Room B
9:00 – 10:00 Invited Talk
Chair: Hiroshi Nagamochi

Peter Eades.
Some Constrained Notions of Planarity

10:00 – 10:30 Coffee Break
Distributed Algorithm
Chair: Andrew Goldberg
Chair: Takeshi Tokuyama
10:30 – 10:55 Fedor V. Fomin, Petr A. Golovach, Alexander Hall, Matúš Mihalák, Elias Vicari and Peter Widmayer. How to Guard a Graph? Ehsan Chiniforooshan, Arash Farzan and Mehdi Mirzazadeh. Evaluation of General Set Expressions
10:55 – 11:20 Paola Flocchini, Bernard Mans and Nicola Santoro. Tree Decontamination with Temporary Immunity Ferdinando Cicalese and Martin Milanič. Computing with Priced Information: When the Value Makes the Price
11:20 – 11:45 Greg Aloupis, Sébastien Collette, Erik D. Demaine, Stefan Langerman, Vera Sacristán and Stefanie Wuhrer. Reconfiguration of Cube-Style Modular Robots Using O(log n) Parallel Moves Kazuhisa Makino and Hirotaka Ono. Deductive Inference for the Interiors and Exteriors of Horn Theories
11:45 – 12:10 Yoann Dieudonné and Franck Petit. Squaring the Circle with Weak Mobile Robots Michael R. Fellows, Daniel Meister, Frances A. Rosamond, R. Sritharan and Jan Arne Telle. Leaf Powers and Their Properties: Using the Trees
12:10– 14:00 Lunch (Patio Restaurant)
Approximation Algorithm II
Chair: Sandor Fekete
Computational Biology
Chair: Lars Arge
14:00– 14:25 Ali Çivril and Malik Magdon-Ismail. Deterministic Column Based Matrix Reconstruction via Greedy Approximation of SVD Cheng-Wei Luo, Hsiao-Fei Liu, Peng-An Chen and Kun-Mao Chao. Minkowski Sum Selection and Finding
14:25– 14:50 Naveen Garg, Amit Kumar and Muralidhara V N. Minimizing Total Flow-Time: the Unrelated Case Leo van Iersel and Steven Kelk. Constructing the Simplest Possible Phylogenetic Network from Triplets
14:50 – 15:15 Karl Bringmann and Tobias Friedrich. Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects Jaroslaw Byrka, Sylvain Guillemot and Jesper Jansson. New Results on Optimizing Rooted Triplets Consistency
15:15 – 15:40 Christian Glaßer. Space-Efficient Informational Redundancy M. Oğuzhan Külekci. A Method to Overcome Computer Word Size limitation in Bit-Parallel Pattern Matching
15:40 – 16:00 Coffee Break
Computational Geometry I
Chair: Pat Morin
Complexity I
Chair: Anastasios Viglas
16:00 – 16:25 [Best Student Paper] Ludmila Scharf and Marc Scherfenberg. Inducing Polygons of Line Arrangements Jin-Yi Cai and Pinyan Lu. Signature Theory in Holographic Algorithms
16:25 – 16:50 Danny Z. Chen and Ewa Misiolek. Free-form Surface Partition in 3-D David Buchfuhrer. The Complexity of SPP Formula Minimization
16:50 – 17:15 Christian Knauer and Marc Scherfenberg. Approximate Nearest Neighbor Search under Translation Invariant Hausdorff Distance Eric Goles, Cedric Little and Ivan Rapaport. Understanding a Non-Trivial Cellular Automaton by Finding Its Simplest Underlying Communication Protocol
17:15 – 17:40 Marc van Kreveld, Maarten Löffler and Joseph S.B. Mitchell. Preprocessing Imprecise Points and Splitting Triangulations Hiroki Morizumi and Genki Suzuki. Negation-Limited Inverters of Linear Size
17:40 – 18:05 Harish Doraiswamy and Vijay Natarajan. Efficient Output-Sensitive Construction of Reeb Graphs Giovanni Di Crescenzo and Helger Lipmaa. 3-Message NP Arguments in The BPK Model with Optimal Soundness and Zero-Knowledge
19:00 – 19:30 Free Drink
19:30 – 22:00 Conference Dinner