Program

10:30	Benjamin Scheidt and Nicole Schweikardt Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation (abstract) PRESENTER: Benjamin Scheidt
10:55	Julien Clément and Antoine Genitrini An iterative approach for counting reduced ordered binary decision diagrams (abstract) PRESENTER: Julien Clément
11:20	Faisal Abu-Khzam, Henning Fernau and Kevin Mann Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes (abstract) PRESENTER: Kevin Mann
11:45	Antonis Achilleos and Aggeliki Chalki Counting Computations with Formulae: Logical Characterisations of Counting Complexity Classes (abstract) PRESENTER: Aggeliki Chalki

10:30-12:10 Session 3B: Graphs 1

Chair:

Marthe Bonamy

Location: Amphi G

10:30	Vera Chekan and Stefan Kratsch Tight Algorithmic Applications of Clique-Width Generalizations (abstract) PRESENTER: Vera Chekan
10:55	Michael Lampis, Nikolaos Melissinos and Manolis Vasilakis Parameterized Max Min Feedback Vertex Set (abstract) PRESENTER: Manolis Vasilakis
11:20	Dibyayan Chakraborty, Jérémie Chalopin, Florent Foucaud and Yann Vaxès Isometric path complexity of graphs (abstract) PRESENTER: Jérémie Chalopin
11:45	Jonas Schmidt and Thomas Schwentick Dynamic constant-time parallel graph algorithms with sub-linear work (abstract) PRESENTER: Jonas Schmidt

12:10-14:00Lunch Break

14:00-15:15 Session 4A: Automata and Formal Languages 1

Chair:

Alessio Mansutti

Location: Amphi F

14:00	Pablo Barcelo, Diego Figueira and Rémi Morvan Separating Automatic Relations (abstract) PRESENTER: Rémi Morvan
14:25	Florian Frank, Stefan Milius and Henning Urbat Positive Data Languages (abstract) PRESENTER: Florian Frank
14:50	Taisei Nogami and Tachio Terauchi On the Expressive Power of Regular Expressions with Backreferences (abstract) PRESENTER: Taisei Nogami

14:00-15:15 Session 4B: Graphs, complexity and logic

Chair:

Ramanujan Sridharan

Location: Amphi G

14:00	Samir Datta, Asif Khan and Anish Mukherjee Dynamic Planar Embedding is in DynFO (abstract) PRESENTER: Asif Khan
14:25	Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniel Paulusma, Siani Smith and Erik Jan van Leeuwen Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs (abstract) PRESENTER: Matthew Johnson
14:50	Tim Seppelt Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors (abstract)

15:15-15:45Coffee Break

15:45-17:00 Session 5A: Query complexity, Matrix, and Polynomoids

Chair:

Julien Clément

Location: Amphi F

15:45	Diptarka Chakraborty, Gunjan Kumar and Kuldeep Meel Support Size Estimation: The Power of Conditioning (abstract) PRESENTER: Gunjan Kumar
16:10	Nader Bshouty On Property Testing of the Binary Rank (abstract)
16:35	Meng-Tsung Tsai, Shi-Chun Tsai and Tsung-Ta Wu Dependent k-Set Packing on Polynomoids (abstract) PRESENTER: Tsung-Ta Wu

15:45-17:00 Session 5B: Logic in Computer Science 1

Chair:

Rémi Morvan

Location: Amphi G

15:45	Yoshiki Nakamura On the Finite Variable-Occurrence Fragment of the Calculus of Relations with Bounded Dot-Dagger Alternation (abstract)
16:10	Christoph Haase, Alessio Mansutti and Amaury Pouly On Polynomial-Time Decidability of k-Negations Fragments of FO Theories (Extended Abstract) (abstract) PRESENTER: Alessio Mansutti
16:35	Jakub Bulín and Michael Kompatscher Short definitions in constraint languages (abstract) PRESENTER: Michael Kompatscher

Tuesday, August 29th

View this program: with abstracts session overview talk overview

08:30-08:55Coffee Break

08:55-09:00 Session 6: MFCS 2024

Presentation of the upcoming MFCS 2024 by Jerzy Marcinkowski, member of the MFCS steering commitee.

Location: Amphi F

09:00-10:00 Session 7

Invited Talk

Chair:

Jérôme Leroux

Location: Amphi F

09:00

Laura Kovacs

Algebraic Reasoning for (Un)Solvable Loops

10:00-10:30Coffee Break

10:30-12:10 Session 8A: Algebraic Methods

Chair:

Laura Kovacs

Location: Amphi F

10:30	Léo Paviet Salomon and Pascal Vanier Realizing finitely presented groups as projective fundamental groups of SFTs (abstract) PRESENTER: Léo Paviet Salomon
10:55	Vikraman Arvind and Pushkar Joglekar Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization (abstract) PRESENTER: Pushkar Joglekar
11:20	Jack H. Lutz, Satyadev Nandakumar and Subin Pulari A Weyl Criterion for Finite-State Dimension and Applications (abstract) PRESENTER: Subin Pulari
11:45	Peter Mayr On the complexity dichotomy for the satisfiability of systems of term equations over finite algebras (abstract)

10:30-12:10 Session 8B: Parametrized Complexity

Chair:

Yogesh Dahiya

Location: Amphi G

10:30	Jana Holznigenkemper, Christian Komusiewicz, Nils Morawietz and Bernhard Seeger On the Complexity of Computing Time Series Medians under the Move-Split-Merge Metric (abstract) PRESENTER: Jana Holznigenkemper
10:55	Adele Anna Rescigno and Luisa Gargano A FPT Algorithm for Spanning Trees with Few Branch Vertices Parameterized by Modular Width (abstract) PRESENTER: Luisa Gargano
11:20	Cornelius Brand, Viktoriia Korchemna and Michael Skotnica Deterministic Constrained Multilinear Detection (abstract) PRESENTER: Cornelius Brand
11:45	Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar and Tomohiro Koana FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges (abstract) PRESENTER: Fedor V. Fomin

12:10-14:00Lunch Break

14:00-15:15 Session 9A: Constructive Logics and Semantics

Chair:

Thomas Schwentick

Location: Amphi F

14:00	Michal Konecny, Sewon Park and Holger Thies Formalizing Hyperspaces for Extracting Efficient Exact Real Computation (abstract) PRESENTER: Holger Thies
14:25	Liron Cohen, Bruno da Rocho Paiva, Vincent Rahli and Ayberk Tosun Inductive Continuity via Brouwer Trees (abstract) PRESENTER: Ayberk Tosun
14:50	Clotilde Bizière, Erich Grädel and Matthias Naaf Locality Theorems in Semiring Semantics (abstract) PRESENTER: Clotilde Bizière

14:00-15:15 Session 9B: Distributed and Parallel Algorithms

Chair:

Ivan Bliznets

Location: Amphi G

14:00	Noy Biton, Reut Levi and Moti Medina Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations (abstract) PRESENTER: Moti Medina
14:25	Veeti Ahvonen, Damian Heiman, Lauri Hella and Antti Kuusisto Descriptive complexity for distributed computing with circuits (abstract) PRESENTER: Antti Kuusisto
14:50	Margarita Mikhelson and Alexander Okhotin Parallel enumeration of parse trees (abstract) PRESENTER: Margarita Mikhelson

15:15-15:45Coffee Break

15:45-17:00 Session 10A: Cryptography, Security, and Quantum

Chair:

Yvan Le Borgne

Location: Amphi F

15:45	Jiří Balun, Tomáš Masopust and Petr Osička Speed Me up if You Can: Conditional Lower Bounds on Opacity Verification (abstract) PRESENTER: Jiří Balun
16:10	Charles Bouillaguet, Florette Martinez and Damien Vergnaud Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator (abstract) PRESENTER: Florette Martinez
16:35	Francois Le Gall, Masayuki Miyamoto and Harumichi Nishimura Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications (abstract) PRESENTER: Masayuki Miyamoto

15:45-17:00 Session 10B: Verification 1

Chair:

Jérôme Leroux

Location: Amphi G

15:45	Shaull Almagor, Arka Ghosh, Tim Leys and Guillermo Pérez The Geometry of Reachability in Continuous Vector Addition Systems with States (abstract) PRESENTER: Tim Leys
16:10	Michaël Cadilhac, Arka Ghosh, Guillermo Perez and Ritam Raha Parikh One-Counter Automata (abstract) PRESENTER: Arka Ghosh
16:35	Sergei Ovcharov OBDD(join) Proofs Cannot be Balanced (abstract)

Wednesday, August 30th

View this program: with abstracts session overview talk overview

08:30-09:00Coffee Break

09:00-10:00 Session 11

Invited Talk

Chair:

David Peleg

Location: Amphi F

09:00

Paul Spirakis

Some Algorithmic Problems on Temporal Graphs (abstract)

10:00-10:30Coffee Break

10:30-12:10 Session 12A: Computational and Dynamic Complexity

Chair:

Paul Spirakis

Location: Amphi F

10:30	Manon Blanc and Olivier Bournez A characterization of functions computable in polynomial time and space over the reals with discrete ordinary differential equations. Simulation of Turing machines with analytic discrete ordinary differential equations. (abstract) PRESENTER: Manon Blanc
10:55	Satyadev Nandakumar, Akhil S and Prateek Vishnoi Effective Continued Fraction Dimension versus Effective Hausdorff Dimension of Reals (abstract) PRESENTER: Akhil S
11:20	Fabian Egidy, Christian Glaßer and Martin Herold Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP (abstract) PRESENTER: Martin Herold
11:45	Jonas Schmidt, Thomas Schwentick and Jennifer Todtenhoefer On the work of dynamic constant-time parallel algorithms for regular tree languages and context-free languages (abstract) PRESENTER: Jennifer Todtenhoefer

10:30-12:10 Session 12B: Games 1

Chair:

Hugo Gimbert

Location: Amphi G

10:30	Léonard Brice, Jean-Francois Raskin and Marie Van Den Bogaard Rational Verification for Nash and Subgame-perfect Equilibria in Graph Games (abstract) PRESENTER: Léonard Brice
10:55	Marianne Akian, Stéphane Gaubert, Ulysse Naepels and Basile Terver Solving irreducible stochastic mean-payoff games and entropy games by relative Krasnoselskii-Mann iteration (abstract) PRESENTER: Stéphane Gaubert
11:20	Tom Demeulemeester and Jannik Peters Relaxed core stability for hedonic games with size-dependent utilities (abstract) PRESENTER: Jannik Peters
11:45	Thomas Dissaux, Foivos Fioravantes, Harmender Gahlawat and Nicolas Nisse Recontamination helps a lot to hunt a rabbit (abstract) PRESENTER: Foivos Fioravantes

12:10-14:00Lunch Break

17:00-19:00 Cité du Vin (Bordeaux Wine City)

The social event takes place on Wednesday afternoon. It will start at "Cité du Vin » (Bordeaux Wine City) at 17h00, we will meet at this place before the visit. This place is directly accessible from Talence using Tram B, stop « Cité du Vin ». The museum visit lasts for about 2 hours, including tasting a glass of wine, more details there.

20:00-22:00 Diner at restaurant "Le café du port"

We will go to the restaurant « Le café du port », there. The dinner will start at 20h00. The restaurant is accessible from the museum by walking (40 minutes of a gentle walk by the quays) or by Tramway B, bus 91 or even by boat « Batcub 3 ».

Thursday, August 31st

View this program: with abstracts session overview talk overview

08:30-09:00Coffee Break

09:00-10:00 Session 13

Invited Talk

Chair:

Spyros Angelopoulos

Location: Amphi F

09:00

Joan Boyar

Online Algorithms with Predictions

10:00-10:30Coffee Break

10:30-12:10 Session 14A: Operational Search

Chair:

Fedor V. Fomin

Location: Amphi F

10:30	Spyros Angelopoulos Competitive Search in the Line and the Star with Predictions (abstract)
10:55	Niklas Hahn and Michalis Xefteris The Covering Canadian Traveller Problem Revisited (abstract) PRESENTER: Michalis Xefteris
11:20	Dimitris Fotakis, Evangelia Gergatsouli, Charilaos Pipis, Miltiadis Stouras and Christos Tzamos Graph Connectivity with Noisy Queries (abstract) PRESENTER: Miltiadis Stouras
11:45	Martijn van Ee, Tim Oosterwijk, Rene Sitters and Andreas Wiese Exact and approximation algorithms for routing a convoy through a graph (abstract) PRESENTER: Martijn van Ee

10:30-12:10 Session 14B: Cuts and Graphs

Chair:

Alexander Okhotin

Location: Amphi G

10:30	Felicia Lucke, Daniel Paulusma and Bernard Ries Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius (abstract) PRESENTER: Felicia Lucke
10:55	Ivan Bliznets and Vladislav Epifanov MaxCut Above Guarantee (abstract) PRESENTER: Ivan Bliznets
11:20	Eduard Eiben, Diptapriyo Majumdar and Ramanujan Sridharan Finding a Highly Connected Steiner Subgraph and its Applications (abstract) PRESENTER: Ramanujan Sridharan

12:10-14:00Lunch Break

14:00-15:15 Session 15A: Online Algorithms

Chair:

Joan Boyar

Location: Amphi F

14:00	Elisabet Burjons, Matthias Gehnen, Henri Lotze, Daniel Mock and Peter Rossmanith The Online Simple Knapsack Problem with Reservation and Removability (abstract) PRESENTER: Matthias Gehnen
14:25	Yasuaki Kobayashi, Kazuhiro Kurita and Kunihiro Wasa Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids (abstract) PRESENTER: Kazuhiro Kurita
14:50	Spyros Angelopoulos and Shahin Kamali Rényi-Ulam Games and Online Computation with Imperfect Advice (abstract) PRESENTER: Spyros Angelopoulos

14:00-15:15 Session 15B: Verification 2 and Computational Complexity

Chair:

Vincent Penelle

Location: Amphi G

14:00	Stefan Ratschan Deciding Predicate Logical Theories of Real-Valued Functions (abstract)
14:25	Nicolas Waldburger Checking Presence Reachability Properties on Parameterized Shared-Memory Systems (abstract)
14:50	Arkadev Chattopadhyay, Yogesh Dahiya and Meena Mahajan Query Complexity of Search Problems (abstract) PRESENTER: Yogesh Dahiya

15:15-15:45Coffee Break

15:45-17:00 Session 16A: Circuit Complexity

Chair:

Pushkar Joglekar

Location: Amphi F

15:45	Benedikt Pago Lower bounds for Choiceless Polynomial Time via Symmetric XOR-circuits (abstract)
16:10	Mika Göös, Ziyi Guan and Tiberiu Mosnoi Depth-3 Circuits for Inner Product (abstract) PRESENTER: Ziyi Guan
16:35	Kei Uchizawa and Haruki Abe Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy (abstract) PRESENTER: Kei Uchizawa

15:45-17:00 Session 16B: Games 2

Chair:

Stéphane Gaubert

Location: Amphi G

15:45	Christel Baier, Krishnendu Chatterjee, Tobias Meggendorfer and Jakob Piribauer Entropic Risk for Turn-Based Stochastic Games (abstract) PRESENTER: Jakob Piribauer
16:10	Harmender Gahlawat and Meirav Zehavi Parameterized Analysis of the Cops and Robber Game (abstract) PRESENTER: Harmender Gahlawat
16:35	Mohan Dantam and Richard Mayr Approximating the Value of Energy-Parity Objectives in Simple Stochastic Games (abstract) PRESENTER: Mohan Dantam

Friday, September 1st

View this program: with abstracts session overview talk overview

08:30-09:00Coffee Break

09:00-10:00 Session 17

Invited Talk

Chair:

David Peleg

Location: Amphi F

09:00

Artur Czumaj

Modern Parallel Algorithms (abstract)

10:00-10:30Coffee Break

10:30-12:10 Session 18A: Automata and Formal Languages 2

Chair:

Olivier Bournez

Location: Amphi F

10:30	Matthew Earnshaw and Paweł Sobociński String Diagrammatic Trace Theory (abstract) PRESENTER: Matthew Earnshaw
10:55	Daniel Alexander Spenner Decomposing Finite Languages (abstract)
11:20	Alex Rose and Alexander Okhotin Probabilistic Input-driven Pushdown Automata (abstract) PRESENTER: Alexander Okhotin
11:45	Laure Daviaud and Andrew Ryzhikov Universality and Forall-Exactness of Cost Register Automata with Few Registers (abstract) PRESENTER: Laure Daviaud

10:30-12:10 Session 18B: Graphs 2

Chair:

Jérémie Chalopin

Location: Amphi G

10:30	Neeldhara Misra and Saraswati Nanoti Spartan Bipartite Graphs are Essentially Elementary (abstract) PRESENTER: Saraswati Nanoti
10:55	Deniz Ağaoğlu Çağırıcı, Onur Çağırıcı, Jan Derbisz, Tim Hartmann, Petr Hliněný, Jan Kratochvíl, Tomasz Krawczyk and Peter Zeman Recognizing H-graphs – beyond circular-arc graphs (abstract) PRESENTER: Tim Hartmann
11:20	Yixin Cao, Hanchun Yuan and Jianxin Wang Modification Problems toward Proper (Helly) Circular-arc Graphs (abstract) PRESENTER: Hanchun Yuan
11:45	Guozhen Rong, Yongjie Yang and Wenjun Li A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs (abstract) PRESENTER: Yongjie Yang

12:10-14:00Lunch Break

14:00-15:40 Session 19A: Parametrized Complexity

Chair:

Luisa Gargano

Location: Amphi F

14:00	Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, Nidhi Purohit and Saket Saurabh Fixed-Parameter Algorithms for Fair Hitting Set Problems (abstract) PRESENTER: Madhumita Kundu
14:25	Giacomo Ortali, Fabrizio Montecchiani, Giuseppe Liotta, Carla Binucci and Tommaso Piselli On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges (abstract) PRESENTER: Giacomo Ortali
14:50	Manuel Lafond and Weidong Luo Parameterized Complexity of Domination Problems Using Restricted Modular Partitions (abstract) PRESENTER: Weidong Luo
15:15	Satyabrata Jana, Daniel Lokshtanov, Soumen Mandal, Ashutosh Rai and Saket Saurabh Parameterized Approximation Scheme for Feedback Vertex Set (abstract) PRESENTER: Satyabrata Jana

14:00-15:40 Session 19B: Logic in Computer Science 2

Chair:

Peter Mayr

Location: Amphi G

14:00	Juha Kontinen, Max Sandström and Jonni Virtema Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity (abstract) PRESENTER: Max Sandström
14:25	Theodoros Papamakarios A super-polynomial separation between resolution and cut-free sequent calculus (abstract)
14:50	Isa Vialard Ordinal measures of the set of finite multisets (abstract)
15:15	Dylan Braithwaite, Jules Hedges and Toby St Clere Smithe The Compositional Structure of Bayesian Inference (abstract) PRESENTER: Dylan Braithwaite