| 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 | |||