Program
- Plenary talks will be in the LaBRI amphitheatre (building A30).
- Talks for the A track will be in amphitheatre A of building A29.
- Talks for the B track will be in LaBRI amphitheatre.
Thursday 21 February
| 8:00-9:00 |
Registration LaBRI, conference site, Building A30, University Bordeaux I |
|
| 9:00-10:00 |
Maxime Crochemore and Lucian Ilie, Understanding Maximal Repetitions in Strings Chair: S. Albers |
|
| Coffee break | ||
| Session 1A Chair: R. Klasing |
Session 1B Chair: A. Muscholl |
|
|---|---|---|
| 10:20-10:45 |
Mirela Damian, Robin Flatland, Joseph O'Rourke and Suneeta Ramaswami. Connecting Polygonizations via Stretches and Twangs |
Laurent Bienvenu, Andrej Muchnik, Alexander Shen and Nikolay Vereshchagin. Limit complexities revisited |
| 10:45-11:10 |
Atlas F. Cook IV and Carola Wenk. Geodesic Fréchet Distance Inside a Simple Polygon |
Pilar Albert, Elvira Mayordomo, Philippe Moser and Sylvain Perifel. Pushdown Compression |
| 11:10-11:35 |
Iyad A. Kanj and Ljubomir Perković. On Geometric Spanners of Euclidean and Unit Disk Graphs |
Angsheng Li and Mingji Xia. A Theory for Valiant's Matchcircuits |
| Coffee break | ||
| Session 2A Chair: E. Grandjean |
Session 2B Chair: M. Lohrey |
|
|---|---|---|
| 11:50-12:15 |
Chandan Saha. Factoring Polynomials over Finite Fields using Balance Test |
Jean-François Dufourd. Discrete Jordan Curve Theorem: A proof formalized in Coq with hypermaps |
| 12:15-12:40 |
Javier Esparza, Stefan Kiefer and Michael Luttenberger. Convergence Thresholds of Newton's Method for Monotone Polynomial Equations |
Edith Hemaspaandra and Henning Schnoor. On the Complexity of Elementary Modal Logics |
| Lunch break | ||
| Session 3A Chair: C. Gavoille |
Session 3B Chair: C. Löding |
|
| 14:30-14:55 |
Johan M. M. van Rooij and Hans L. Bodlaender. Design by Measure and Conquer - A Faster Exact Algorithm for Dominating Set |
Jacques Sakarovitch and Rodrigo de Souza. On the Decomposition of k-valued Rational Relations |
| 14:55-15:20 |
Andreas Björklund, Thore Husfeldt, Petteri Kaski and Mikko Koivisto. Trimmed Moebius Inversion and Graphs of Bounded Degree |
Wouter Gelade and Frank Neven. Succinctness of the Complement and Intersection of Regular Expressions |
| 15:20-15:45 |
Julián Mestre. Lagrangian Relaxation and Partial Cover |
Antti Valmari and Petri Lehtinen. Efficient Minimization of DFAs with Partial Transition Functions |
| Coffee break | ||
| Session 4A Chair: V. Diekert |
Session 4B Chair: I. Walukiewicz |
|
| 16:00-16:25 |
Chao Chen and Daniel Freedman. Quantifying Homology Classes |
Patricia Bouyer, Nicolas Markey, Joël Ouaknine, Philippe Schnoebelen and James Worrell. On Termination for Faulty Channel Machines |
| 16:25-16:50 |
Joshua Brody and Amit Chakrabarti. Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound |
Diana Fischer, Erich Grädel and Łukasz Kaiser. Model Checking Games for the Quantitative μ-Calculus |
| 16:50-17:15 |
Artur Jeż and Alexander Okhotin. Complexity of solutions of equations over sets of natural numbers |
Dietrich Kuske. Compatibility of Shelah and Stupp's and Muchnik's Iterations with Fragments of Monadic Second Order Logic |
| 17:45-19:00 |
Wine conference and degustation in Chateau Peixotto (City council of Talence) Walking distance from LaBRI (see map) |
|
Friday 22 February
| 9:00-10:00 |
Mihalis Yannakakis, Equilibria, Fixed Points and Complexity Classes Chair: K. Iwama |
|
| Coffee break | ||
| Session 5A Chair: A. Raspaud |
Session 5B Chair: P. Gastin |
|
|---|---|---|
| 10:20-10:45 |
Samir Datta, Raghav Kulkarni and Sambuddha Roy. Deterministically Isolating a Matching in Bipartite Planar Graphs |
Andris Ambainis. Quantum search with variable times |
| 10:45-11:10 |
Thomas Erlebach, Michael Hoffmann, Danny Krizanc, Matúš Mihal'ák and Rajeev Raman. Computing Minimum Spanning Trees with Uncertainty |
Bill Rosgen. Distinguishing Short Quantum Computations |
| 11:10-11:35 |
Éric Colin de Verdière and Alexander Schrijver. Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs |
Alexis Ballier, Bruno Durand and Emmanuel Jeandel. Structural aspects of tilings |
| Coffee break | ||
| Session 6A Chair: Ch. Frougny |
Session 6B Chair: S. Albers |
|
| 11:50-12:15 |
Markus Bläser and Christian Hoffmann. On the Complexity of the Interlace Polynomial |
Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela and Leen Stougie. Minimizing Flow Time in the Wireless Gathering Problem |
| 12:15-12:40 |
Thomas Thierauf and Fabian Wagner. The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace |
Zvi Lotker, Boaz Patt-Shamir and Dror Rawitz. Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental |
| Lunch break | ||
| Session 7A Chair: N. Hanusse |
Session 7B Chair: M. Bousquet-Mélou |
|
| 14:30-14:55 |
Ulrich Meyer. On Dynamic Breadth-First Search in External-Memory |
Jui-Yi Kao, Jeffrey Shallit and Zhi Xu. The Frobenius Problem in a Free Monoid |
| 14:55-15:20 |
Shachar Lovett. Lower bounds for adaptive linearity tests |
Jean-Éric Pin and Pedro V. Silva. A Mahler's theorem for functions from words to integers |
| 15:20-15:45 |
Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener and Philipp Woelfel. Tight Bounds for Blind Search on the Integers |
Marni Mishna and Mike Zabrocki. Analytic aspects of the shuffle product |
| Coffee break | ||
| Session 8A Chair: M. Robson |
Session 8B Chair: L. Ségoufin |
|
| 16:00-16:25 |
Iyad A. Kanj, Michael J. Pelsmajer, Marcus Schaefer and Ge Xia. On the Induced Matching Problem |
Felix Klaedtke. Ehrenfeucht-Fraïssé Goes Automatic for Real Addition |
| 16:25-16:50 |
Viet Tung Hoang and Wing-Kin Sung. Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees |
Lukasz Kaiser, Sasha Rubin and Vince Bárány. Cardinality and counting quantifiers on omega-automatic structures |
| 16:50-17:15 |
Mariano Zelke. Weighted Matching in the Semi-Streaming Model |
Tobias Ganzow and Sasha Rubin. Order-Invariant MSO is Stronger than Counting MSO in the Finite |
| 20:00-23:00 |
Banquet in Palais Rohan (City council of Bordeaux) Tram station Pey Berland (see map) |
|
Saturday 23 February
| 9:00-10:00 |
Thomas Schwentick, A Little Bit Infinite? On Adding Data to Finitely Labelled Structures Chair: P. Weil |
|
| Coffee break | ||
| Session 9A Chair: J. Esparza |
Session 9B Chair: J. Karhumäki |
|
|---|---|---|
| 10:20-10:45 |
Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff and Alexander Wolff. Trimming of Graphs, with Application to Point Labeling |
Arist Kojevnikov and Sergey I. Nikolenko. New Combinatorial Complete One-Way Functions |
| 10:45-11:10 |
Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, M. Sohel Rahman and Tomasz Waleń. Improved Algorithms for the Range Next Value Problem and Applications |
Jeff Kinne and Dieter van Melkebeek. Space Hierarchy Results for Randomized Models |
| 11:10-11:35 |
Sören Lauen. Geometric Set Cover and Hitting Sets for Polytopes in R3 |
Venkatesan T. Chakaravarthy and Sambuddha Roy. Finding Irrefutable Certificates for S2p via Arthur and Merlin |
| Coffee break | ||
| Session 10A Chair: B. Vöcking |
Session 10B Chair: W. Thomas |
|
| 11:50-12:15 |
Pinyan Lu and Changyuan Yu. An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines |
Christian Glaßer, Heinz Schmitz and Victor Selivanov. Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages |
| 12:15-12:40 |
Patrick Briest, Martin Hoefer and Piotr Krysta. Stackelberg Network Pricing Games |
Filip Murlak. Weak index versus Borel rank |
| End of conference | ||