Not logged in
Path: Menu > Program

Sunday

17:00-20:00

Registration

Monday

8:00

Registration

8:45

Opening

9:00-10:00

Georg Gottlob

On the Complexity of Ontological Reasoning under Disjunctive Existential Rules

(co-authors: Marco Manna, Michael Morak, Andreas Pieris)

10:30-11:45

SESSION A1

Petr Golovach, Daniel Paulusma and Bernard Ries

Coloring Graphs Characterized by a Forbidden Subgraph

Petr Golovach, Pim Van 'T Hof and Daniel Paulusma

Obtaining Planarity by Contracting Few Edges

Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub and Thomas Thierauf

Planarizing Gadgets for Perfect Matching do not Exist

10:30-11:45

SESSION B1

Robert Ganian, Petr Hlineny, Jaroslav Nesetril, Jan Obdrzalek, Patrice Ossona de Mendez and Reshma Ramadurai

When Trees Grow Low: Shrubs and Fast MSO1

Taolue Chen, Klaus Dräger and Stefan Kiefer

Model Checking Stochastic Branching Processes

Alexander Kartzow and Pawel Parys

Strictness of the Collapsible Pushdown Hierarchy

13:30-14:30

Esko Ukkonen

How to Reconstruct a Genome

15:00-16:40

SESSION A2

Tatiana Starikovskaya

Computing Lempel-Ziv Factorization Online

Laurent Bulteau, Guillaume Fertin and Irena Rusu

Pancake Flipping Is Hard

Jingsen Chen, Stefan Edelkamp, Amr Elmasry and Jyrki Katajainen

In-Place Heap Construction with Optimized Comparisons, Moves, and Cache Misses

Filip Murlak, Michał Ogiński and Marcin Przybyłko

Between tree patterns and conjunctive queries: is there tractability beyond acyclicity?

15:25-16:40

SESSION B2

Cristina Bazgan and Morgan Chopin

The Robust Set problem: parameterized complexity and approximation

Mingyu Xiao and Jiong Guo

A Quadric Vertex Kernel for Feedback Arc Set in Bipartite Tournaments

Dimitris Fotakis and Paraschos Koutris

Online Sum-Radii Clustering

18:00

Welcome raut

Tuesday

9:00-10:00

Antonino Salibra

Scott is always simple

10:30-11:45

SESSION A1

Thomas Weidner

Probabilistic Automata and Probabilistic Logic

Radu Mardare, Prakash Panangaden and Kim Guldstrand Larsen

Take it to the limit: Approximate reasoning for Markov processes

Dorit Pardo and Alexander Rabinovich

A Finite Basis for "Almost Future" Temporal Logic over the Reals

10:30-11:45

SESSION B1

Dietmar Berwanger, Lukasz Kaiser and Simon Leßenich

Solving Counter Parity Games

Marcus Gelderie

Strategy Machines and their Complexity

Angelo Fanelli, Luca Moscardelli and Alexander Skopalik

On the Impact of Fair Best Response Dynamics

13:30-14:30

Nicole Schweikardt

A toolkit for proving limitations of the expressive power of logics

15:00-16:40

SESSION A2

Ville Salo and Ilkka Törmä

Computational Aspects of Cellular Automata on Countable Sofic Shifts

Martin Delacourt and Petr Kurka

Finite State Transducers for Modular Möbius Number Systems

Anthony Widjaja Lin

Weakly-Synchronized Ground Tree Rewriting (with applications to verifying multithreaded programs)

David Janin

Quasi-recognizable vs MSO definable languages of one-dimensional overlapping tiles

15:00-16:40

SESSION B2

Eric Allender, Harry Buhrman, Luke Friedman and Bruno Loff

Reductions to the Set of Random Strings: the Resource-Bounded Case

Giovanni Di Crescenzo and Vadym Fedyukovych

Zero-Knowledge Proofs via Polynomial Representations

Andreas Krebs, Christoph Behle, Pierre Mckenzie and Klaus-Joern Lange

The lower reaches of circuit uniformity

Meena Mahajan, Raghavendra Rao B V and Karteek Sreenivasaiah

Identity Testing, multilinearity testing, and monomials in Read-Once/Twice Formulas and Branching Programs

Wednesday

9:00-10:00

Rolf Niedermeier

New Races in Parameterized Algorithmics

(co-authors: Christian Komusiewicz)

10:30-11:45

SESSION A1

V. Arvind, Johannes Köbler, Sebastian Kuhnert and Yadu Vasudev

Approximate Graph Isomorphism

Klaus Jansen and Stefan Kraft

An Improved Approximation Scheme for Variable-Sized Bin Packing

Jesper Nederlof, Erik Jan van Leeuwen and Ruben van der Zwaan

Reducing a Target Interval to a Few Exact Queries

10:30-11:45

SESSION B1

Lauri Ahlroth and Pekka Orponen

Unordered Constraint Satisfaction Games

Furio Honsell, Marina Lenisa and Rekha Redamalla

Categories of Coalgebraic Games

Stefan Repke and Christof Löding

Regularity Problems for Weak Pushdown ω-Automata and Games

13:30

Conference trip (Tour of Bratislava)

Thursday

9:00-10:00

Igor Walukiewicz

Simple models for recursive schemes

10:30-11:45

SESSION A1

Olivier Bournez, Pierre Fraigniaud and Xavier Koegler

Computing with Large Populations Using Interactions

Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita and Sebastien Tixeuil

Gathering an even number of robots in a symmetric ring without global multiplicity detection

Tom Friedetzky, Leszek Gasieniec, Thomas Gorry and Russell Martin

Observe and remain silent (Communication-less agent location discovery)

10:30-11:45

SESSION B1

Akitoshi Kawamura, Hiroyuki Ota, Carsten Rösnick and Martin Ziegler

Computational Complexity of Smooth Differential Equations

Nicolas de Rugy-Altherre

A Dichotomy Theorem for Homomorphism polynomials

Paul Bell, Mika Hirvensalo and Igor Potapov

Mortality for 2x2 matrices is NP-hard

13:30-14:30

Gerhard J. Woeginger

Transportation under nasty side constraints

15:00-16:40

SESSION A2

Sotiris Nikoletseas, Christoforos Raptopoulos and Paul Spirakis

Maximum Cliques in Graphs with Small Intersection Number and Random Intersection Graphs

Tatsuya Akutsu and Takeyuki Tamura

A Polynomial-Time Algorithm for Computing the Maximum Common Subgraph of Outerplanar Graphs of Bounded Degree

Andreas Emil Feldmann

Fast Balanced Partitioning is Hard, Even on Grids and Trees

Michelangelo Grigni and Hao-Hsiang Hung

Light Spanners in Bounded Pathwidth Graphs

15:00-16:40

SESSION B2

Igor Tunev and Arseny Shur

On Two Stronger Versions of Dejean's Conjecture

Elena Petrova and Arseny Shur

Constructing Premaximal Ternary Square-Free Words of Any Level

Gabriele Fici

A Characterization of Bispecial Sturmian Words

Florin Manea, Robert Mercas and Dirk Nowotka

Fine and Wilf theorem and pseudo-repetitions

19:00

Conference dinner (Restaurant Matyšák)

Friday

9:00-10:00

Mihalis Yannakakis

Computation of Least Fixed Points

10:30-11:45

SESSION A1

Torben Hagerup

Kernels for Edge Dominating Set: Simpler or Smaller

Robert Crowston, Gregory Gutin, Mark Jones, Saket Saurabh and Anders Yeo

Parameterized Study of the Test Cover Problem

Martin Doucha and Jan Kratochvil

Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width

10:30-11:45

SESSION B1

Christos Kapoutsis and Giovanni Pighizzini

Reversal Hierarchies for Small 2DFAs

Katja Losemann, Wim Martens and Matthias Niewerth

Descriptive Complexity of Deterministic Regular Expressions

Eugene Asarin, Nicolas Basset, Aldric Degorre and Dominique Perrin

Generating functions of timed languages

13:30-14:20

SESSION A2

Paul Bonsma

The complexity of rerouting shortest paths

Davide Bilò and Anna Zych

New Advances in reoptimizing the Minimum Steiner Tree problem

13:30-14:20

SESSION B2

Francine Blanchet-Sadri and Sean Simmons

Abelian Pattern Avoidance in Partial Words

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar and Yadu Vasudev

Near-Optimal Expanding Generating Sets for Solvable Permutation Groups

14:50-16:05

SESSION A3

Markus Blaeser and Bodo Manthey

Smoothed Complexity Theory

Matus Mihalak and Jan Christoph Schlegel

Asymmetric Swap-Equilibrium: A Unifying Equilibrium Concept for Network Creation Games

Therese Biedl and Peter Floderus

Drawing planar graphs on points inside a polygon

14:50-16:05

SESSION B3

Manfred Kufleitner and Alexander Lauser

The Join Levels of the Trotter-Weil Hierarchy are Decidable

Tommi Lehtinen

Equations X+A=B and (X+X)+C=(X-X)+D over sets of natural numbers

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Onufry Wojtaszczyk

Sitting closer to friends than enemies, revisited