rooms amphitheatre Bilsky Pasquier for all plenary talks
amphitheatre Bilsky Pasquier for A track amphitheatre Gustave Roussy for B track
Wednesday, February 29th
13:45-14:15 Registration and coffee
14:15-15:45 Iterative Methods in Combinatorial Optimization
R. Ravi [slides #1]
  coffee break
16:00-17:30 second part of the tutorial [slides #2]
Thursday, March 1st
8:00-8:45 Registration and coffee
8:45-9:00 Opening
9:00-10:00 Forms of Determinism for Automata [slides]
Thomas Colcombet
  coffee break
chair Christoph Dürr Thomas Wilke
10:20-10:45 13/9-approximation for Graphic TSP
Marcin Mucha.
Lower bounds on the complexity of MSO1 model-checking
Robert Ganian, Petr Hlineny, Alexander Langer, Jan Obdrzalek, Peter Rossmanith and Somnath Sikdar.
10:45-11:10 Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem
Khaled Elbassioni, Katarzyna Paluch and Anke Van Zuylen.
Weak MSO+U over infinite trees
Mikołaj Bojańczyk and Szymon Toruńczyk.
11:10-11:35 Conflict-free Chromatic Art Gallery Coverage
Andreas Baertschi and Subhash Suri.
Concurrency Makes Simple Theories Hard
Stefan Göller and Anthony Widjaja Lin.
  coffee break
chair Christoph Dürr Thomas Wilke
11:50-12:15 Preemptive and Non-Preemptive Generalized Min Sum Set Cover
Sungjin Im, Maxim Sviridenko and Ruben Van Der Zwaan.
Ehrenfeucht-Fraïssé goes elementarily automatic for structures of bounded degree
Antoine Durand-Gasselin and Peter Habermehl.
12:15-12:40 LP can be a cure for Parameterized Problems
Ramanujan M. S., Venkatesh Raman, Saket Saurabh and Narayanaswamy N. S..
The Field of Reals is not omega-Automatic
Faried Abu Zaid, Erich Grädel and Lukasz Kaiser.
  lunch break
chair Berthold Vöcking Dietrich Kuske
14:30-14:55 Cache-Oblivious Implicit Predecessor Dictionaries with the Working-Set Property
Gerth Stølting Brodal and Casper Kejlberg-Rasmussen.
A Pumping Lemma for Pushdown Graphs of Any Level
Pawel Parys.
14:55-15:20 Linear-Space Data Structures for Range Mode Query in Arrays
Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison and Bryan T. Wilkinson.
The Limits of Decidability for First-Order Logic on CPDA Graphs
Christopher Broadbent.
15:20-15:45 Playing Mastermind With Constant-Size Memory
Benjamin Doerr and Carola Winzen.
The Determinacy of Context-Free Games
Olivier Finkel.
  coffee break
chair Berthold Vöcking Dietrich Kuske
16:00-16:25 Randomized Communication Complexity for Linear Algebra Problems over Finite Fields
Xiaoming Sun and Chengu Wang.
Distribution of the number of accessible states in a random deterministic automaton
Arnaud Carayol and Cyril Nicaud.
16:25-16:50 Variable time amplitude amplification and quantum algorithms for linear algebra problems
Andris Ambainis.
Asymptotic enumeration of Minimal Automata
Frederique Bassino, Julien David and Andrea Sportiello.
16:50-17:15 Trichotomy for Integer Linear Systems Based on Their Sign Patterns
Kei Kimura and Kazuhisa Makino.
Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P)
Artur Jeż.
  free time
18:00... Visit of the musée du quai Branly, RER C pont de l'Alma
Friday, March 2nd
8:30-9:00 Registration and coffee
9:00-10:00 On Randomness in Hash Functions [slides]
Martin Dietzfelbinger
  coffee break
chair R. Ravi Anca Muscholl
10:20-10:45 Efficiently Decodable Compressed Sensing by List-Recoverable Codes and Recursion
Hung Ngo, Ely Porat and Atri Rudra.
Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes
Maurice Jansen and Rahul Santhanam.
10:45-11:10 Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices
Ioannis Koutis, Alex Levin and Richard Peng.
Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth
Michael Elberfeld, Andreas Jakoby and Till Tantau.
11:10-11:35 Mind Change Speed-up for Learning Languages from Positive Data
Sanjay Jain and Efim Kinber.
Monomials in arithmetic circuits: Complete problems in the counting hierarchy
Hervé Fournier, Guillaume Malod and Stefan Mengel.
  coffee break
chair R. Ravi Anca Muscholl
11:50-12:15 Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid minor
Ken-Ichi Kawarabayashi and Yusuke Kobayashi.
On separation question for tree languages
André Arnold, Henryk Michalewski and Damian Niwiński.
12:15-12:40 Improved bounds on Bipartite Matching on surfaces
Samir Datta, Arjun Gopalan, Raghav Kulkarni and Raghunath Tewari.
Regular tree languages, cardinality predicates, and addition-invariant FO
Frederik Harwath and Nicole Schweikardt.
  lunch break
chair Michel de Rougemont Manuel Bodirsky
14:30-14:55 Low Randomness Rumor Spreading via Hashing
George Giakkoupis, Thomas Sauerwald, He Sun and Philipp Woelfel.
Log-supermodular functions, functional clones and counting CSPs
Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg and Mark Jerrum.
14:55-15:20 Stabilization of Branching Queueing Networks
Tomas Brazdil and Stefan Kiefer.
An Approximation Algorithm for #k-SAT
Marc Thurley.
  coffee break
chair Michel de Rougemont Manuel Bodirsky
15:35-16:00 Contraction Checking in Graphs on Surfaces
Marcin Kaminski and Dimitrios Thilikos.
The dimension of ergodic random sequences
Mathieu Hoyrup.
16:00-16:25 Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces
Paul Bonsma.
The Denjoy alternative for computable functions
Laurent Bienvenu, Rupert Hölzl, Joseph Miller and André Nies.
  coffee break
chair Gerhard Woeginger Andris Ambainis
16:40-17:05 Edge-disjoint Odd Cycles in 4-edge-connected Graphs
Ken-Ichi Kawarabayashi and Yusuke Kobayashi.
Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers
László Babai and Youming Qiao.
17:05-17:30 Parameterized Complexity of Connected Even/Odd Subgraph Problems
Fedor V. Fomin and Petr Golovach.
On Computing Pareto Stable Assignments
Ning Chen.
  free time
19:00-21:00 Conference dinner at the restaurant Bouillon Racine, 3 Rue Racine
Saturday, March 3nd
8:30-9:00 Registration and coffee
9:00-10:00 Pseudo-deterministic Algorithms
Shafi Goldwasser
  coffee break
chair Carola Winzen Artur Jeż
10:20-10:45 Optimizing Linear Functions with Randomized Search Heuristics -- The Robustness of Mutation
Carsten Witt.
Constant compression and random weights
Wolfgang Merkle and Jason Teutsch.
10:45-11:10 The Power of Local Search: Maximum Coverage over a Matroid
Yuval Filmus and Justin Ward.
Tying up the loose ends in fully LZW-compressed pattern matching
Pawel Gawrychowski.
11:10-11:35 A (k + 3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems
Justin Ward.
Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P
Volker Diekert, Jürn Laun and Alexander Ushakov.
  coffee break
chair Carola Winzen Artur Jeż
11:50-12:15 Balanced Partitions of Trees and Applications
Andreas Emil Feldmann and Luca Foschini.
Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified
Kai-Min Chung, Henry Lam, Zhenming Liu and Michael Mitzenmacher.
12:15-12:40 Motion planning with pulley, rope, and baskets
Christian Eggermont and Gerhard J. Woeginger.
On treewidth and related parameters of random geometric graphs
Dieter Mitsche and Guillem Perarnau.
  The End