|
|
|
|
|
9:00 - 10:00 Albert Atserias: Four subareas of the theory of constraints, and their links (invited talk)
10:00 - 10:30 coffee break
10:30 - 12:00 Session A
Ezra Resnick, Yoram Bachrach, Reshef Meir and Jeffrey Rosenschein: The Cost of Stability in Network Flow Games
Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis and Evi Papaioannou: Energy-efficient communication in multi-interface wireless networks
Vincenzo Auletta, Paolo Penna and Giuseppe Persiano: Private capacities in mechanism design
10:30 - 12:00 Session B
Diego Figueira and Luc Segoufin: Future-looking logics on data words and trees
Tony Tan: On Pebble Automata for Data Languages with Decidable Emptiness Problem
Lukasz Kaiser: Synthesis for Structure Rewriting Systems
12:00 - 15:00 lunch
15:00 - 17:00 Session A
Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis and Maria Kyropoulou: An improved approximation bound for spanning star forest and color saving
Johannes Köbler and Sebastian Kuhnert: The k-tree isomorphism problem is complete for logspace
Ivona Bezakova and William A. Rummler: Sampling and Counting Edge Covers in 3-Regular Graphs
Kyriaki Ioannidou, George Mertzios and Stavros Nikolopoulos: The Longest Path Problem is Polynomial on Interval Graphs
15:00 - 17:00 Session B
Manfred Kufleitner and Pascal Weil: On FO2 quantifier alternation over words
Wouter Gelade, Marc Gyssens and Wim Martens: Regular expressions with Counting: Weak versus Strong Determinism
Arturo Carpi and Flavio D'Alessandro: The synchronization problem for locally strongly transitive automata
Pawel Gawrychowski and Artur Jez: Hyper-minimising and k-hyper-minimising the automaton in O (|δ| log n)
9:30 - 10:30 Peter Widmayer: How to Sort a Train (invited talk)
10:30 - 11:00 coffee break
11:00 - 12:30 Session A
Anuj Dawar and Yuguo He: Parameterized Complexity Classes under Logical Reductions
Yi Cao, Joseph Culberson and Lorna Stewart: DP-complete Problems Derived from Extremal NP-complete Properties
Sagarmoy Dutta and Piyush P Kurur: Representing groups on graphs
11:00 - 12:30 Session B
Ahmet Kara, Volker Weber, Martin Lange and Thomas Schwentick: On the Hybrid Extension of CTL and CTL+
Arne Meier, Martin Mundhenk, Thomas Schneider, Michael Thomas, Volker Weber and Felix Weiss: The Complexity of Satisfiability for Fragments of Hybrid Logic - Part I
Stanislav Zivny, David A. Cohen and Peter G. Jeavons: The Expressive Power of Binary Submodular Functions
12:30 - 15:00 lunch
15:00 - 16:00 Didier Caucal: Synchronization of regular automata (invited talk)
16:00 - 16:30 coffee break
16:30 - 18:00 Session A
Daniel Kirsten: An Algebraic Characterization of Semirings for which the Support of a Recognizable Series is Always Recognizable
Tomi Kärki, Anne Lacroix and Michel Rigo: On the recognizability of self-generating sets
Francisco Claude and Gonzalo Navarro: Indexing Straight-Line Programs
16:30 - 18:00: Session B
Bakhadyr Khoussainov, Jiamou Liu and Imran Khaliq: A Dynamic Algorithm for Reachability Games Played on Trees
Sven Schewe: From Parity and Payoff Games to Linear Programming
Marco Faella: Admissible Strategies in Infinite Games over Graphs
9:30 - 10:30 Muthu Muthukrishnan: Stochastic Data Streams (invited talk)
10:30 - 11:00 coffee break
11:00 - 12:30 Session A
Mathieu Chapelle, Frédéric Mazoit and Ioan Todinca: Constructing Brambles
Petr Golovach and Pinar Heggernes: Choosability of P5-free graphs
Alessandro Bianco, Marco Faella, Fabio Mogavero and Aniello Murano: Balanced Paths in Colored Graphs
11:00 - 12:30 Session B
Giulio Manzonetto: A general class of models of H*
Marco Gaboardi, Luca Roversi and Luca Vercelli: Multiplicative Exponential Linear Logic can be levelled
Delia Kesner and Fabien Renaud: The prismoid of resources
12:30 - 15:00 lunch
9:30 - 10:30 Pavlos Spirakis: Recent Advances in Population Protocols (invited talk)
10:30 - 11:00 coffee break
11:00 - 12:30 Session A
Periklis Papakonstantinou: On the Structure of Optimal Greedy Computation (for Job Scheduling)
Kai Plociennik: A Probabilistic PTAS for Shortest Common Superstring
Feodor Dragan and Yang Xiang: How to use spanning trees to navigate in graphs
11:00 - 12:30 Session B
Rupert Hölzl, Thorsten Kräling and Wolfgang Merkle: Time-bounded Kolmogorov complexity and Solovay functions
Xizhong Zheng and Robert Rettinger: Points on Computable Curves of Computable Lengths
Tadao Takaoka: Partial Solution and Entropy
12:30 - 15:00 lunch
15:00 - 16:00 Javier Esparza: Stochastic process creation (invited talk)
16:00 - 16:30 coffee break
16:30 - 18:00 Session A
Gaétan Richard:(Un)decidability of injectivity and surjectivity in one-dimensional sand automaton
Jarkko Kari, Pascal Vanier and Thomas Zeume: Bounds on non-surjective cellular automata
Violetta Lonati and Matteo Pradella: Snake-Deterministic Tiling Systems
16:30 - 18:00 Session B
Irénée Briquel and Pascal Koiran: A Dichotomy Theorem for Polynomial Evaluation
Martin Roetteler: Quantum algorithms for hidden shift problems: quadratics and functions of large Gowers norm
Kohtaro Tadaki: Partial Randomness and Dimension of Recursively Enumerable Reals
9:30 - 10:30 Krishnendu Chatterjee, Thomas A. Henzinger and Florian Horn: Stochastic Games with Finitary Objectives (invited talk)
10:30 - 11:00 coffee break
11:00 - 12:30 Session A
Sotiris Nikoletseas, Christoforos Raptopoulos and Paul Spirakis: Colouring Non-Sparse Random Intersection Graphs
Adrian Kosowski and Alfredo Navarra: Graph Decomposition for Improving Memoryless Periodic Exploration
Michael Fellows, Jiong Guo, Hannes Moser and Rolf Niedermeier: A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
11:00 - 12:30 Session B
Bernd Borchert, Pierre McKenzie and Klaus Reinhardt: Few Product Gates but Many Zeros
Kei Uchizawa, Eiji Takimoto and Takao Nishizeki: Size and Energy of Threshold Circuits Computing Mod Functions
Vikraman Arvind and Pushkar Joglekar: Arithmetic Circuits, Monomial Algebras and Finite Automata
12:30 - 15:00 lunch
15:00 - 16:30 Session A
Julien Degorre, Marc Kaplan, Sophie Laplante and Jérémie Roland: The communication complexity of non-signaling distributions
Nadja Betzler and Britta Dorn: Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
Paolo D'Arco, Alfredo De Santis, Anna Lisa Ferrara and Barbara Masucci: Security and Tradeoffs of the Akl-Taylor Scheme and its Variants
15:00 - 16:30 Session B
Mark Braverman, Stephen Cook, Pierre McKenzie, Rahul Santhanam and Dustin Wehr: Branching Programs for Tree Evaluation
Alexander Kartzow: FO Model Checking on Nested Pushdown Trees
P. Madhusudan and Mahesh Viswanathan: Query Automata for Nested Words
Social events:
welcome party (Monday evening)
leasure time (Wednesday afternoon)
conference dinner (Friday evening)