Thursday 4th, 2010

8:00
9:00
Registration
9:00
10:00

Rolf Niedermeier, University of Jena
Reflections on Multivariate Algorithmics and Problem Parameterization
Chair : Jean-Yves Marion
Amphi C -
HAL, LIPIcs

Coffee Break

Session 1A - Amphi C
Chair : Jiří Sgall
Session 1B - C005
Chair : Serge Grigorieff

10:20
10:45

Neelesh Khanna and Surender Baswana.
Approximate shortest paths avoiding a failed vertex: Optimal size data structures for unweighted graphs
HAL, LIPIcs

Pierre Guillon and Gaétan Richard.
Revisiting the Rice Theorem of Cellular Automata
HAL, LIPIcs

10:45
11:10

Victor Chen, Elena Grigorescu and Ronald de Wolf.
Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation
HAL, LIPIcs

David Doty, Jack Lutz, Matt Patitz, Scott Summers and Damien Woods.
Intrinsic Universality in Self-Assembly
HAL, LIPIcs

11:10
11:35

George Mertzios, Ignasi Sau and Shmuel Zaks.
The Recognition of Tolerance and Bounded Tolerance Graphs
HAL, LIPIcs

Julien Cervelle, Enrico Formenti and Pierre Guillon.
Ultimate Traces of Cellular Automata

HAL, LIPIcs

Coffee Break

Session 2A - Amphi C
Chair : Pavan Aduri
Session 2B - C005
Chair : Enrico Formenti

11:50
12:15

Dominik Scheder.
Unsatisfiable Linear CNF Formulas Are Large and difficult to construct explicitely
HAL, LIPIcs

Sergey Bravyi, Aram Harrow and Avinatan Hassidim.
Quantum algorithms for testing properties of distributions

HAL, LIPIcs

12:15
12:40

Edward A. Hirsch and Dmitry Itsykson.
On optimal heuristic randomized semidecision procedures, with application to proof complexity
HAL, LIPIcs

Francois Le Gall.
An Efficient Quantum Algorithm for some Instances of the Group Isomorphism Problem
HAL, LIPIcs

Lunch Break

Session 3A - Amphi C
Chair : Jack Lutz
Session 3B - C005
Chair : Stephan Merz

14:30
14:55

Adrian Dumitrescu and Csaba Toth.
Long non-crossing configurations in the plane
HAL, LIPIcs

Angelo Montanari, Gabriele Puppis, Pietro Sala and Guido Sciavicco.
Decidability of the interval temporal logic ABB over the natural numbers
HAL, LIPIcs

14:55
15:20

David Peleg and Liam Roditty
Relaxed spanners for directed disk graphs

HAL, LIPIcs

Stefan Göller and Markus Lohrey.
Branching-time model checking of one-counter processes
HAL, LIPIcs

15:20
15:45

Mark de Berg, Fred van Nijnatten, Rene Sitters, Gerhard Woeginger and Alexander Wolff.
The Traveling Salesman Problem Under Squared Euclidean Distances
HAL, LIPIcs

Javier Esparza, Andreas Gaiser and Stefan Kiefer.
Computing Least Fixed Points of Probabilistic Systems of Polynomials

HAL, LIPIcs

Coffee Break

Session 4A - Amphi C
Chair : Thomas Schwentick
Session 4B - C005
Chair : Jean-Yves Marion

16:00
16:25

Adrian Dumitrescu and Minghui Jiang.
Dispersion in unit disks
HAL, LIPIcs

Serge Grigorieff and Pierre Valarcher.
Evolving MultiAlgebras unify all usual sequential computation models
HAL, LIPIcs

16:25
16:50

Rustem Takhanov.
Dichotomy theorem for general Minimum Cost Homomorphisms Problem
HAL, LIPIcs

Lutz Schröder and Dirk Pattinson.
Named Models in Coalgebraic Hybrid Logic
HAL, LIPIcs

16:50
17:15

Andreas Björklund.
Exact Covers via Determinants
HAL, LIPIcs

Artur Jez and Alexander Okhotin.
On equations over sets of integers

HAL, LIPIcs

18H30 : Guided tour at the museum des Beaux Arts, 3 place stanislas
19H30 : Welcome cocktail at museum des Beaux Arts

Friday 5th, 2010

 

Session 5A - Amphi C
Chair : Etienne Grandjean
Session 5B - C005
Chair : Berthold Vöcking

9:00
9:25

Lance Fortnow, Jack H. Lutz and Elvira Mayordomo.
Inseparability and Strong Hypotheses for Disjoint NP Pairs
HAL, LIPIcs

Shiri Chechik and David Peleg.
Fault Tolerant uncapacitated facility location
HAL, LIPIcs

9:25
9:50

Dániel Marx, Barry O'Sullivan and Igor Razgon.
Treewidth reduction for constrained separation and bipartization problems
HAL, LIPIcs

H.L. Chan, T.W. Lam, L.K. Lee and H.F. Ting.
Continuous Monitoring of Distributed Data Streams over a Time-based Sliding Window
HAL, LIPIcs

9:50
10:15

Bireswar Das, Jacobo Torán and Fabian Wagner.
Restricted Space Algorithms for Isomorphism On Bounded Treewidth Graphs

HAL, LIPIcs

Marcin Bienkowski, Marek Klonowski, Miroslaw Korzeniowski and Dariusz Kowalski.
Dynamic Sharing of a Multiple Access Channel
HAL, LIPIcs

Coffee Break

Session 6A - Amphi C
Chair : Osamu Watanabe
Session 6B - C005
Chair :

10:35
11:00

Nader Bshouty and Hanna Mazzawi.
Optimal Query Complexity for Reconstructing Hypergraphs

HAL, LIPIcs

Paul Dütting, Monika Henzinger and Ingmar Weber.
Sponsored Search, Market Equilibria, and the Hungarian Method
HAL, LIPIcs

11:00
11:25

Claire Mathieu, Ocan Sankur and Warren Schudy.
Online Correlation Clustering
HAL, LIPIcs

Felix Brandt, Felix Fischer and Markus Holzer.
On Iterated Dominance, Matrix Elimination, and Matched Paths
HAL, LIPIcs

Coffee Break

11:40
12:40

Jacques Stern, Ecole Normale Supérieure
Mathematics, Cryptology, Security
Chair : Pierrick Gaudry
Amphi C - HAL, LIPIcs

Lunch Break

Session 7A - Amphi C
Chair : Rolf Niedermeier
Session 7B - C005
Chair :

14:30
14:55

Sourav Chakraborty, Eldar Fischer, Oded Lachish and Raphael Yuster.
Two-phase algorithms for the parametric shortest path problem

HAL, LIPIcs

Laszlo Babai, Anandam Banerjee, Raghav Kulkarni and Vipul Naik.
Evasiveness and the Distribution of Prime Numbers
HAL, LIPIcs

14:55
15:20

Frederic Dorn, Fedor Fomin, Daniel Lokshtanov, Venkatesh Raman and Saket Saurabh. Beyond  Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs
HAL, LIPIcs

Ryan Williams.
Alternation-Trading Proofs, Linear Programming, and Lower Bounds
HAL, LIPIcs

15:20
15:45

Fedor Fomin and Yngve Villanger.
Finding Induced Subgraphs via Minimal Triangulations
HAL, LIPIcs

Vikraman Arvind and Srikanth Srinivasan.
The Remote Point Problem, Small Bias spaces, and Expanding Generator sets

HAL, LIPIcs

Coffee Break

Session 8A - Amphi C
Chair : Ernst Mayr
Session 8B - C005
Chair : Pascal Weil

16:00
16:25

Bireswar Das, Samir Datta and Prajakta Nimbhorkar.
Log-space Algorithms for Paths and Matchings in k-trees
HAL, LIPIcs

Alexander Kartzow.
Collapsible pushdown graphs of level 2 are tree-automatic
HAL, LIPIcs

16:25
16:50

Maurice Jansen.
Weakening Assumptions for Deterministic Subexponential Time Non-Singular Matrix Completion
HAL, LIPIcs

Dietrich Kuske.
Is Ramsey's theorem omega-automatic?
HAL, LIPIcs

16:50
17:15

Xiaoyang Gu, John Hitchcock and Pavan Aduri.
Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses
HAL, LIPIcs

Xavier Allamigeon, Stephane Gaubert and Eric Goubault. The tropical double description method
HAL, LIPIcs

20:00 Gale Dinner at the "Grand Salon" of the town hall of Nancy, 1 Place Stanislas (very closed to the Beaux Arts Museum)

 

Saturday 6th, 2010

9h
10h

Mikolaj Bojanczyk, Warsaw University
Beyond Omega-Regular Languages
Chair : Wolfgang Thomas
Amphi C - HAL, LIPIcs

Coffee Break

Session 9A - Amphi C
Chair : Markus Bläser
Session 9B - C005
Chair : Angelo Montanari

10:20
10:45

Jiri Fiala, Marcin Kaminski, Bernard Lidicky and Daniel Paulusma.
The k-in-a-path problem for claw-free graphs
HAL, LIPIcs

Laszlo Egri, Andrei Krokhin, Benoit Larose and Pascal Tesson.
The complexity of the list homomorphism problem for graphs
HAL, LIPIcs

10:45
11:10

Michal Adamaszek and Anna Adamaszek.
Large-girth roots of graphs
HAL, LIPIcs

Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius and David Richerby.
The Complexity of Approximating Bounded-Degree Boolean #CSP

HAL, LIPIcs

11:10
11:35

Vladimir Braverman, Kai-Min Chung, Zhenming Liu, Michael Mitzenmacher, Rafail Ostrovsky
AMS Without 4-Wise Independence on Product domains
HAL, LIPIcs

Michael Kowalczyk and Jin-Yi Cai.
Holant Problems for Regular Graphs with Complex Edge Functions

HAL, LIPIcs

Coffee Break

Session 10A - Amphi C
Chair : Mikolaj Bojanczyk
Session 10B - C005
Chair : Jiří Sgall

11:50
12:15

Frederic Dorn.
Planar Subgraph Isomorphism Revisited

HAL, LIPIcs

Leah Epstein, Asaf Levin, Julian Mestre and Danny Segev
Improved Approximation Guarantees for Weighted Matching  in the Semi-Streaming Model

HAL, LIPIcs

12:15
12:40

Jens M. Schmidt.
Construction Sequences and Certifying 3-Connectedness
HAL, LIPIcs

Łukasz Jeż.
A 4/3-competitive randomised algorithm for online scheduling of packets with agreeable deadline
HAL, LIPIcs