Room A Room B Room C
08:00 Registration
08:50 Opening

Session Chair: Erzsébet Csuhaj-Varjú

09:00 Invited Talk: Krishnendu Chatterjee

Partial-observation Stochastic Reachability and Parity Games

10:00 Coffee break

Session Chair: Kristoffer Arnsfelt Hansen Session Chair: Antonio Restivo
10:30 Petr Golovach Cewei Cui, Zhe Dang, Thomas R. Fischer and Oscar Ibarra

Editing to a Connected Graph of Given Degrees Information Rate of Some Classes of Non-Regular Languages: An Automata-Theoretic Approach
10:55 Marek Cygan, Dániel Marx, Marcin Pilipczuk and Michal Pilipczuk Andrzej Murawski, Steven Ramsay and Nikos Tzevelekos

Hitting Forbidden Subgraphs in Graphs of Bounded Treewidth Reachability in Pushdown Register Automata
11:20 Stefan Fafianie and Stefan Kratsch Tim Smith

Streaming Kernelization On Infinite Words Determined by Indexed Languages
11:45 Ramanujan M. S., Sudeshna Kolay, Pranabendu Misra and Saket Saurabh Salvatore La Torre, Margherita Napoli and Gennaro Parlato

Parameterized Approximations via d-Skew Symmetric Multicut A Unifying Approach for Multistack Pushdown Automata
12:10 Lunch

Session Chair: Ian Munro Session Chair: Bodo Manthey Session Chair: Zoltán Ésik
14:00 Tetsuo Asano, David Kirkpatrick, Koutaro Nakagawa and Osamu Watanabe Peter Jonsson and Johan Thapper Viliam Geffert and Alexander Okhotin

O(sqrt(n))-Space and Polynomial-Time Algorithm for the Planar Directed Graph Reachability Affine Consistency and the Complexity of Semilinear Constraints Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
14:25 Ivona Bezakova and Zachary Langley Nicolas Delfosse, Zhentao Li and Stéphan Thomassé Christian Choffrut and Bruno Guillon

Minimum Planar Multi-Sink Cuts with Connectivity Priors A Note on the Minimum Distance of Quantum LDPC Codes An Algebraic Characterization of Unary Two-Way Transducers
14:50 Stefan Felsner, Kolja Knauer, George Mertzios and Torsten Ueckerdt Hartmut Klauck and Supartha Podder Sven Schewe and Thomas Methrayil Varghese

Intersection Graphs of L-Shapes and Segments in the Plane Two Results about Quantum Messages Determinising Parity Automata
15:15 Matteo Pontecorvi, Vijaya Ramachandran and Meghana Nasre Thomas Decker, Gábor Ivanyos, Raghav Kulkarni, Youming Qiao and Miklos Santha Namit Chaturvedi and Marcus Gelderie

Betweenness Centrality - Incremental and Faster An Efficient Quantum Algorithm for Finding Hidden Parabolic Subgroups in the General Linear Group Classifying Recognizable Infinitary Trace Languages Using Word Automata
15:40 Coffee break

Session Chair: Valentine Kabanets Session Chair: Dániel Marx Session Chair: Dietrich Kuske
16:10 Kristoffer Arnsfelt Hansen, Balagopal Komarath, Jayalal Sarma, Sven Skyum and Navid Talebanfard Georgios Stamoulis Nathanaël Fijalkow and Charles Paperman

Circuit Complexity of Properties of Graphs with Constant Planar Cutwidth Approximation Algorithms for Bounded Color Matchings via Convex Decompositions Monadic Second-Order Logic with Arbitrary Monadic Predicates
16:35 Joan Boyar and Magnus Gausdal Find Maurits de Graaf and Bodo Manthey Filip Mazowiecki, Filip Murlak and Adam Witkowski

The Relationship Between Multiplicative Complexity and Nonlinearity Probabilistic Analysis of Power Assignments Monadic Datalog and Regular Tree Pattern Queries
17:00 Beate Bollig Hadas Shachnai, Ariella Voloshin and Shmuel Zaks Yijia Chen and Moritz Mueller

On the Complexity of Some Ordering Problems Flexible Bandwidth Assignment with Application to Optical Networks Bounded Variable Logic, Parameterized Logarithmic Space, and Savitch's Theorem
17:25 Andris Ambainis and Krišjānis Prūsis Christian Glasser and Maximilian Witek Pierre Bourhis, Michael Morak and Andreas Pieris

A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes Towards Efficient Reasoning Under Guarded-Based Disjunctive Existential Rules
19:00 Welcome party in room Attila of Mercure Hotel Buda


Room A Room B Room C

Session Chair: Zoltán Ésik

09:00 Invited Talk: Achim Jung

A Modal Belnap Logic

10:00 Coffee break

Session Chair: Ian Munro

10:30 Invited Talk: Peter Bro Miltersen

Computer Poker and Computational Game Theory

Session Chair: Martin Dietzfelbinger

11:30 Presentation of the Best Paper Award

Eric Allender and Bireswar Das : Zero Knowledge and Circuit Minimization

12:00 Lunch

Session Chair: Vijaya Ramachandran Session Chair: Christian Choffrut Session Chair: Werner Kuich
14:00 Othon Michail and Paul Spirakis Julien Cassaigne, Frid Anna, Svetlana Puzynina and Luca Zamboni Daniel Bundala and Joel Ouaknine

Traveling Salesman Problems in Temporal Graphs Subword Complexity and Decomposition of the Set of Factors Advances in Parametric Real-Time Reasoning
14:25 Nils Kriege and Petra Mutzel Florin Manea, Mike Müller, Dirk Nowotka and Shinnosuke Seki Stépán Holub, Galina Jirasková and Tomás Masopust

Finding Maximum Common Biconnected Subgraphs in Series-Parallel Graphs Generalised Lyndon-Schützenberger Equations On Upper and Lower Bounds on the Length of Alternating Towers
14:50 Rémy Belmonte, Pim Van 'T Hof, Marcin Kamiński and Daniel Paulusma Yuto Nakashima, Takashi Okabe, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda Tim Smith

Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set Inferring Strings from Lyndon factorization A Pumping Lemma for Two-Way Finite Transducers
15:15 Carl Feghali, Matthew Johnson and Daniel Paulusma Arturo Carpi, Gabriele Fici, Stepan Holub, Jakub Oprsal and Marinella Sciortino Timo Jolivet and Jarkko Kari

A Reconfigurations Analogue of Brook’s Theorem Universal Lyndon Words Undecidable Properties of Self-Affine Sets and Multi-Tape Automata
15:40 Coffee break

Session Chair: Eric Allender Session Chair: Krishnendu Chatterjee Session Chair: Masayuki Takeda
16:10 Gergely Kovásznai, Helmut Veith, Andreas Fröhlich and Armin Biere Thomas Colcombet, Laure Daviaud and Florian Zuleger Julien Cassaigne, Gabriele Fici, Luca Quadro Zamboni and Marinella Sciortino

On the Complexity of Symbolic Verification and Decision Problems in Bit-Vector Logic Size-Change Abstraction and Max-Plus Automata Cyclic Complexity of Words
16:35 Olaf Beyersdorff, Leroy Chew and Mikolas Janota Ines Marusic and James Worrell Marcello M. Bersani, Matteo Rossi and Pierluigi San Pietro

On Unification of QBF Resolution-Based Calculi Complexity of Equivalence and Learning for Multiplicity Tree Automata Logic Characterization of Timed (Non-)Regular Languages
17:00 Dmitry Itsykson and Dmitry Sokolov Jean-Baptiste Courtois and Sylvain Schmitz Michał Wrona

Lower Bounds for Splittings by Linear Combinations Alternating Vector Addition Systems with States Tractability Frontier for Dually-Closed Ord-Horn Quantified Constraint Satisfaction Problems
17:25 Peter Jonsson, Victor Lagerkvist, Johannes Schmidt and Hannes Uppman

Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis


Room A Room B Room C

Session Chair: Kristoffer Arnsfelt Hansen

09:00 Invited Talk: Christian Sohler

What Does the Local Structure of a Planar Graph Tell Us about its Global Structure?

10:00 Coffee break

Session Chair: Christian Choffrut

10:30 Invited Talk: Cyril Nicaud

Random Deterministic Automata

Session Chair: Erzsébet Csuhaj-Varjú

11:30 Presentation of the Best Student Paper Award:

Thomas Zeume : The Dynamic Descriptive Complexity of k-Clique

12:00 Lunch
16:00 Social event: Sightseeing tour

19:00 Social event: Banquet


Room A Room B Room C

Session Chair: Eric Allender

09:00 Invited Talk: Alexander Sherstov

Communication Complexity Theory: Thirty-Five Years of Set Disjointness

10:00 Coffee break

Session Chair: Peter Bro Miltersen Session Chair: Cyril Nicaud
10:30 Vittorio Bilo', Angelo Fanelli, Michele Flammini, Gianpiero Monaco and Luca Moscardelli Wied Pakusa, Erich Grädel, Faried Abu Zaid and Martin Grohe

The Price of Envy-Freeness in Machine Scheduling Choiceless Polynomial Time on Structures with Small Abelian Colour Classes
10:55 Julie De Pril, János Flesch, Jeroen Kuipers, Gijs Schoenmakers and Koos Vrieze Kord Eickmeyer, Michael Elberfeld and Frederik Harwath

Existence of Secure Equilibrium in Multi-Player Games with Perfect Information Expressivity and Succinctness of Order-Invariant Logics on Depth-Bounded Structures
11:20 Akaki Mamageishvili, Matus Mihalak and Simone Montemezzani Antti Kuusisto and Emanuel Kieronski

An H_{n/2} Upper Bound on the Price of Stability of Undirected Network Design Games Complexity and Expressivity of Uniform One-Dimensional Fragment with Equality
11:45 Jiehua Chen, Piotr Faliszewski, Rolf Niedermeier and Nimrod Talmon Abhisekh Sankaran, Bharat Adsul and Supratik Chakraborty

Combinatorial Voter Control in Elections A Generalization of the Łoś-Tarski Preservation Theorem over Classes of Finite Structures
12:10 Lunch

Session Chair: Alexander Sherstov Session Chair: Petr Golovach Session Chair: Achim Jung
14:00 Josep Diaz and George Mertzios Ron Y. Pinter, Hadas Shachnai and Meirav Zehavi Martin Lang, Christof Löding and Amaldev Manuel

Minimum Bisection is NP-hard on Unit Disk Graphs Deterministic Parameterized Algorithms for the Graph Motif Problem Definability and Transformations for Cost Logics and Automatic Structures
14:25 Jan Kratochvil, Jan Arne Telle and Marek Tesař Leizhen Cai and Junjie Ye Furio Honsell, Luigi Liquori and Ivan Scagnetto

Computational Complexity of Covering Three-Vertex Multigraphs Dual Connectedness of Edge-Bicolored Graphs and Beyond LLFP: Side Conditions and External Evidence as Monads
14:50 Shuichi Hirahara and Akitoshi Kawamura Hasan Abasi, Nader Bshouty, Ariel Gabizon and Elad Haramaty Jesus Dominguez and Maribel Fernandez

On Characterizations of Randomized Computation Using Plain Kolmogorov Complexity On r-Simple k-Path Relating Nominal and Higher-Order Rewriting
15:15 Vyas Ram Selvam Ruiwen Chen, Valentine Kabanets and Nitin Saurabh Tomasz Gogacz, Henryk Michalewski, Matteo Mio and Michał Skrzypczak

The Two Queries Assumption and Arthur-Merlin Classes An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas Measure Properties of Game Tree Languages
15:40 Coffee break

Session Chair: Christian Glasser Session Chair: Christian Sohler Session Chair: Alexander Okhotin
16:10 Matthew Johnson, Daniel Paulusma and Anthony Stewart Moshe Lewenstein, Ian Munro, Yakov Nekrich and Sharma V. Thankachan Martin Huschenbett, Dietrich Kuske and Georg Zetzsche

Knocking Out P_k-Free Graphs Document Retrieval with One Wildcard The Monoid of Queue Actions
16:35 Ivan Kováč, Ivana Selečéniová and Monika Steinová Chien-Chung Huang and Sebastian Ott Marie-Pierre Béal, Michel Blockelet and Catalin Dima

On the Clique Editing Problem New Results for Non-Preemptive Speed Scaling Sofic-Dyck Shifts
17:00 René Van Bevern, Robert Bredereck, Jiehua Chen, Vincent Froese, Rolf Niedermeier and Gerhard Woeginger Thomas Erlebach, Michael Hoffmann and Frank Kammer Sven Schewe and Thomas Methrayil Varghese

Network-Based Dissolution Query-Competitive Algorithms for Cheapest Set Problems under Uncertainty Tight Bounds for Complementing Parity Automata
17:25 Jeremy Kun and Lev Reyzin Riko Jacob, Tobias Lieber and Nodari Sitchinava

On Coloring Resilient Graphs On the Complexity of List Ranking in the Parallel External Memory Model


Room A Room B Room C

Session Chair: Martin Dietzfelbinger

09:00 Invited Talk: Dániel Marx

Every Graph is Easy Or Hard: Dichotomy Theorems for Graph Problems

10:00 Coffee break

Session Chair: Martin Dietzfelbinger Session Chair: Marie-Pierre Béal
10:30 Nathanaël Fijalkow, Hugo Gimbert, Florian Horn and Youssouf Oualhadj Angelo Montanari, Gabriele Puppis and Pietro Sala

Two Recursively Inseparable Problems for Probabilistic Automata Decidability of the Interval Temporal Logic AA ̄BB ̄ over the Rationals
10:55 Akitoshi Kawamura and Hiroyuki Ota Roy Mennicke

Small Complexity Classes for Computable Analysis Model Checking Concurrent Recursive Programs using Local Temporal Logics
11:20 Eric Allender, Nikhil Balaji and Samir Datta Achim Blumensath, Thomas Colcombet and Olivier Carton

Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs Asymptotic Monadic Second-Order Logic
11:45 Suryajith Chillara and Partha Mukhopadhyay Florian Bruse

On the Limits of Depth Reduction at Depth-3 over Small Finite Fields Alternating Parity Krivine Automata
12:10 Closing

12:20 Lunch