Location

MFCS 2026 will be held in Paris, France, in the building "Halles aux Farines" in the campus des Grands Moulins of the University of Paris, in the 13th arrondissement. The campus is located near the Bibliothèque François Mitterrand, and is easily accessible by public transportation.

A map of the building can be found here.

Talks happen in amphitheater 1A and 4C. Rooms 123C, 125C, and 027C can also be used by the participants for working.

Schedule

Sunday, 13h00-21h00: Young Researcher's Forum

The forum’s aim is to offer an opportunity for young researchers (master’s students, PhD candidates and postdocs) to meet, to discuss, as well as to engage with more experienced researchers on different aspects of scientific research and career.

13h-13h30 Presentations

13h30-14h The work of a Program Committee

Daniela Petrișan

14h30-15h00 An introduction to standards and the standardisation process, or lost and confused at IETF

Juliusz Chroboczek

15h30-16h Research and Curiosity

Michal Koucký

16h30-17h30 Panel Discussion

Daniela Petrișan, Tatiana Starikovskaya, Ryan Williams

18h00 Game evening and dinner at the board game café Playin (map).

Monday, 9h00-10h05 in 1A: Invited speaker 1

9h00 Welcome words

9h05 Homotopy theory in complexity of the graph homomorphism problem

Jakub Opršal [+]

Abstract: I will talk about an emerging new application of homotopy theory in computational complexity of combinatorial problems, more precisely *homomorphism problems*. Homomorphism problems appear under many names, including *constraint satisfaction problems* and conjunctive database queries.

A prime example of a homomorphism problem is graph colouring; by a colouring of a graph with *k* colours, I mean an assignment of colours to vertices under which no edge is monochromatic—this is equivalent to the existence of a homomorphism to the clique with *k* vertices. Graph 3-colouring is a prototypical example of an NP-complete problem.

There are many variations on this problem whose complexity remains widely open. For example, although it is generally believed that colouring a 3-colourable graph with a fixed number of colours is NP-hard, only the hardness of colouring of such a graph with 5 colours is known (and shown only in 2019).

I will give an overview of several related results about variations of graph colouring that share a common theme of using a method based on tools from topological combinatorics and on ideas of Lovász [J. Comb. Theory, Ser. A, 25(3):319-324, 1978].

Monday, 10h30-12h10 in 1A: Discrete algorithms

10h30 Finding Shortest Reconfiguration Sequence on Independent Set Polytopes

Takahiro Suzuki, Jean Cardinal, Kevin Mann, Akira Suzuki, Yuma Tamura, and Xiao Zhou

10h55 The Complexity of Edge-Induced Greedy Subgraph Building Algorithms within P

Zohair Raza Hassan, and Edith Hemaspaandra

11h20 Sharp Thresholds for Temporal Motifs and Doubling Time in Random Temporal Graphs

Henry Austin, George B. Mertzios, and Paul Spirakis

11h45 Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery

Hanno von Bergen, Larissa Fastenau, Enna Gerhard, Nicola Lorenz, Stephanie Maaz, Amer Mouawad, Roman Rabinovich, Nicole Schirrmacher, Daniel Schmand, Sebastian Siebertz, and Mai Trinh

Monday, 10h30-12h10 in 4C: CSP and models of computation

10h30 When Darwin met Ianus: dichotomies of expressivity

Moritz Schöbi, Johanna Brunar, and Michael Pinsker

10h55 The Polynomial Hierarchy and ωω-categorical CSPs

Santiago Guzmán Pro, and Jakub Rydval

11h20 Primitive Recursion without Composition: Dynamical Characterizations, from Neural Networks to Polynomial ODEs

Olivier Bournez

Monday, 14h00-15h40 in 1A: Computational complexity

14h00 Complexity of Clique-Guarded First-Order Logic with Counting

Steffen van Bergerem, Johannes Friedrich Lange, and Nicole Schweikardt

14h25 On the Complexity of Locally Dense Lattices

Shuichi Hirahara, and Kazuki Ogitsuka

14h50 The Power of Small Symmetries

Nikita Gaevoy

15h15 Sublinear Time Algorithms for Abelian Group Property Testing

Nader Bshouty

Monday, 14h00-15h40 in 4C: Fixed-parameter tractability

14h00 Parameterized Complexity of Efficient Sortation

Robert Ganian, Hung Hoang, and Simon Wietheger

14h25 Finding b-colorings Using Feedback Edges

Jakub Balabán

14h50 Counting Equitable kk-Colorings in Graphs of Bounded Clique-width

Holger Dell, Thore Husfeldt, and Amir Nikabadi

15h15 On the Parameterized Complexity of Bounded-Density Vertex Deletion

Jakob Raupach, Tom-Lukas Breitkopf, Anton Herrmann, and André Nichterlein

Monday, 16h10-17h25 in 1A: Computational geometry

16h10 Counting All Lattice Rectangles in the Square Grid in Near-Linear Time

Dmitry Babichev, and Sergey Babichev

16h35 Freeze-Tag with Return

Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Gabriel Le Bouder, Taïssir Marcé, and Nils Morawietz

17h00 Segment Watchman Routes

Anna Brötzner, Omrit Filtser, Bengt J. Nilsson, Christian Rieck, and Christiane Schmidt

Monday, 16h10-17h25 in 4C: Rewriting, logic and categories

16h10 Functorial Semantics for First-Order Theories

Filippo Bonchi, Alessandro Di Giorgio, Roberto Di Virgilio, and Pawel Sobocinski

16h35 Hypergraphs for Compact Closed Categories

Alessandro Di Giorgio, and Callum Reader

17h00 Quantitative equational rewriting

Besik Dundua, Georg Ehling, Santiago Escobar, Maribel Fernandez, and Temur Kutsia

Monday, 18h30 in La Felicità, 5 Parv. Alan Turing, 75013 Paris (meet at 18:00 at the esplanade next to the conference venue): Cocktail party

Tuesday, 9h00-10h00 in 1A: Invited speaker 2

9h00 Highly-efficient local proofs and codes

Noga Ron-Zewi [+]

Abstract: Interactive oracle proofs (IOPs) extend the classical notion of probabilistically-checkable proofs (PCPs) by allowing a verifier to interact with a prover over a small number of rounds, while querying the prover’s messages in only a few locations.

A recent line of work gave highly-efficient IOPs outperforming state-of-the-art PCPs, for example, constant-round and constant-query (ZK-)IOPs with only a linear (and even approaching the witness length) amount of communication, as well as (ZK-)IOPs with linear-time prover complexity. These constructions were leveraged in turn to obtain highly-efficient succinct arguments and zero-knowledge proofs.

The improved efficiency was obtained by replacing polynomial-based codes, commonly used in such proof systems, with more efficient (tensor-based) codes. In particular, these constructions bypassed a barrier imposed by the need to encode the computation using a multiplication code.

In the talk I will survey these highly-efficient IOP constructions, and highlight some interesting open problems raised by these works.

Tuesday, 10h30-12h10 in 1A: Computational complexity

10h30 Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials

Balagopal Komarath, and Rohit Narayanan

10h55 The Descriptive Complexity of Relation Modification Problems

Florian Chudigiewitsch, Marlene Gründel, Christian Komusiewicz, Nils Morawietz, and Till Tantau

11h20 Randomized and quantum approximate matrix multiplication

Simon Apers, Arjan Cornelissen, and Samson Wang

11h45 Nearly Tight Bounds on the Block Number of Boolean Functions in Terms of Sensitivity

Sourav Chakraborty, and Anna Gal

Tuesday, 10h30-12h10 in 4C: Fixed-parameter tractability

10h30 A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth

Jakob Greilhuber, and Roohani Sharma

10h55 Increasing arc-connectivity by bounded- and fixed-size inversions

Lucas Picasarri-Arrieta, and Florian Hörsch

11h20 Connectivity Augmentation of Plane Graphs

Krishnan Dehaleesan, Asif Khan, and Pranabendu Misra

11h45 A Congestion Parameter for Depth-First Graph Traversals

Codaline Bourotte, Gwendal Ducloz, Pekka Orponen, and Shinnosuke Seki

Tuesday, 14h00-15h40 in 1A: Quantum interactive protocols

14h00 Multi-Prover Interactive Proof Systems with Leakage

Vahid R. Asadi, Atsuya Hasegawa, and Francois Le Gall

14h25 En Route to a Standard QMA1 vs. QCMA Oracle Separation

David Miloschewsky, Supartha Podder, and Dorian Rudolph

14h50 Towards a universal gateset for $QMA_1$

Dorian Rudolph

15h15 A slightly improved upper bound for quantum statistical zero-knowledge

Yupan Liu, François Le Gall, and Qisheng Wang

Tuesday, 14h00-15h40 in 4C: Automata and formal languages

14h00 On the size complexity of two-way finite automata with drop-once pebbles

Georgy Kipriyanov, and Alexander Okhotin

14h25 Constant-Time Dynamic Enumeration of Word Infixes in a Regular Language

Antoine Amarilli, Sven Dziadek, and Luc Segoufin

14h50 Hamming distance between finite transducers

Silvio Vescovo, Luc Dartois, Ismaël Jecker, and Pierre-Cyrille Héam

15h15 Distinguishing elements in semigroups

Markus Lohrey, Alexander Thumm, and Julio Xochitemol

Tuesday, 16h10-17h25 in 1A: Algebraic circuits

16h10 Satisfiability of multivalued circuits with lists

Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski, and Armin Weiß

16h35 On $CC^0$ Lower Bounds for AND via Torus Polynomials

Vaibhav Krishan, and Jayalal Sarma

17h00 On the Tension Between Full-Rankness and Self-Reducibility for Set-Multilinear Polynomials

Deepanshu Kush

Tuesday, 16h10-17h25 in 4C: Proof theory and lambda calculus

16h10 Bilateralism with incompatible proofs and refutations

Victor Barroso-Nascimento, Maria Osório, and Elaine Pimentel

16h35 On Jumps, Interactions, and Intersection Types

Stefano Catozi, Ugo Dal Lago, and Gabriele Vanoni

17h00 Compression for Coinductive Rewriting and the Cut-Elimination of Non-Wellfounded Proofs

Rémy Cerda, and Alexis Saurin

Wednesday, 9h00-10h00 in 1A: Invited speaker 3

9h00 Some Recent Developments in Space Complexity

Ryan Williams [+]

Abstract: Given a function, what is the minimal memory necessary to compute it? We will describe old and new algorithmic developments that give surprisingly low-space solutions to this question in many cases. We will survey the recent proof that TIME[t] is in SPACE[sqrt{t log t}] for the multitape Turing machine model, and the engine that makes the proof possible: the amazing Cook-Mertz algorithm for a problem called Tree Evaluation. We will also briefly outline some new developments and generalizations that we've recently proved, pushing the low-space frontier beyond multitape Turing machines.

Wednesday, 10h30-12h10 in 1A: Algorithms

10h30 On Positivity of Exponential-Trigonometric Polynomials and Irrationality Exponents

Pieter Collins, Bernard Hanzon, and Eike Neumann

10h55 Smallest suffixient set maintenance in near-real-time

Dominik Koeppl, and Gregory Kucherov

11h20 Exact Cut Complexity of Equal-Length Proportional Cake Cutting

Yasushi Kawase, and Mohammad Azharuddin Sanpui

11h45 How Long Can the Escaping Ant Be Confined?

Kossi Roland Etse

Wednesday, 10h30-12h10 in 4C: Graphs

10h30 Beating Trivial Time For Tricky Triangle Tasks

Neha Pant, and Ryan Williams

10h55 Generalized snarks, disjoint perfect matchings, and graph covers

Filip Filipi, Jan Kratochvil, and Roman Nedela

11h20 A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs

Babak Ghanbari, and Robert Šámal

11h45 Upper Clique Transversal on Interval Graphs and Beyond

Lars Jaffke, Paloma T. de Lima, and Amir Nikabadi

Wednesday, 14h00-15h15 in 1A: Fixed-parameter tractability

14h00 Lower Bounds for Meta-Reconfiguration

Kord Eickmeyer, Tatsuya Gima, Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, and Daniel Vaz

14h25 Generating minimal redundant and maximal irredundant sets in incidence graphs

Emanuel Castelo, Jérémie Chalopin, Oscar Defrain, and Simon Vilmin

14h50 The Parameterized Complexity of Maximum Span on Natural Matroid Classes

Madhumita Kundu, Ashutosh Rai, Sahiba, and Saket Saurabh

Wednesday, 14h00-15h15 in 4C: Model checking and logic

14h00 Model checking with temporal graphs and their derivative

Binh-Minh Bui-Xuan, Florent Krasnopol, Bruno Monasson, and Nathalie Sznajder

14h25 Characterizing LTL Formulas by Examples

Balder ten Cate, Dana Fisman, Roi Ohayon, and Patrik Sestic

14h50 Order-invariant cluster first-order logic on graph classes of bounded degree

Fatemeh Ghasemi, and Julien Grange

Wednesday, 19h30 in le Train Bleu, inside the train station Gare de Lyon, Pl. Louis Armand hall 1, 75012 (you can gather at 19:00 with a metro ticket at the esplanade): Conference dinner

Thursday, 9h00-10h00 in 1A: Invited speaker 4

9h00 The Art of Balance: Many Facets of Dyck Recognition

Tatiana Starikovskaya [+]

Abstract: The Dyck language, consisting of well-balanced parenthesis sequences, is one of the central objects in formal language theory. The Dyck languages appear naturally in numerous applications: balanced-parenthesis encodings succinctly represent rooted trees, programming languages rely heavily on nested structures, and structured data formats such as XML often utilize a notion of balanced parenthesis sequences.

Dyck languages also arise in computational biology. RNA and DNA secondary structures can often be viewed as "almost balanced" sequences, so understanding the behaviour of the Dyck languages is often an important building block for designing algorithms on such sequences.

In this talk, I will survey several recent developments in Dyck language recognition, highlighting surprising connections to different areas of TCS, including regular language recognition, Boolean matrix multiplication, pattern matching, and graph algorithms. I will also discuss some of the major open questions in the area.

Thursday, 10h30-12h10 in 1A: Computational complexity

10h30 The 2D Ray Tracing Problem using ABCD Lenses and Mirrors is Turing Complete

Rosemary Adejoh, Andreas Jakoby, Sneha Mohanty, and Christian Schindelhauer

10h55 On Equivalent Characterizations of the Polynomial Hierarchy in Abstract Models of Computation

Jeremy C. Kirn, Lucas Meijer, Tillmann Miltzow, and Hans L. Bodlaunder

11h20 Parameterizing the Complexity of Finding Long Paths in DAGs

Ronak Bhadra, Saurya Singh, and Raghunath Tewari

11h45 Space Complexity of Reachability in Simple Path Graphs

Krishnamoorthy Dinesh, and Chandana Sasidharan

Thursday, 10h30-12h10 in 4C: Quantum computation

10h30 Randomized and Quantum Lifting for One-Way Conservative NOF Model

Haoyu Wang, and Pei Wu

10h55 A Framework for Ruling Out Quantum Speedups

Thomas Huffstutler, Upendra Kapshikar, David Miloschewsky, and Supartha Podder

11h20 Hardness of approximation for ground state problems

Carsten Hecht, and Sevag Gharibian

11h45 Product-State Approximation Algorithms for the Transverse Field Ising Model

Vincenzo Lipardi, David Mestel, and Georgios Stamoulis

Thursday, 14h00-15h40 in 1A: Online algorithms

14h00 Forbidden Subgraph Problems with Predictions

Hans-Joachim Böckenhauer, Melvin Jahn, Dennis Komm, and Moritz Stocker

14h25 Forwarding Packets Greedily on the Line

Joan Boyar, Lene Favrholdt, Kim S. Larsen, Kevin Schewior, and Rob van Stee

14h50 Computational Power of Energy-constrained Autonomous Robots under Sequential Schedulers

Caterina Feletti, Paola Flocchini, and Nicola Santoro

15h15 Improved Results for Knapsack with Removal

Matthias Gehnen, Kübra Güven, Valentin Hächler, Dennis Komm, and Richard Královič

Thursday, 14h00-15h40 in 4C: Infinite words and games

14h00 Boolean combinations of omega-rational trace languages: emptiness, rationality, regularity

Dietrich Kuske

14h25 Eve-positional languages: putting order into Büchi automata

Olivier Idir

14h50 Constructible Words Characterize Rational Languages of Words Indexed by Scattered Linear Orderings

Tom Clara, and Thomas Braipson

15h15 Simple Nash Equilibria for Qualitative Multiplayer Games

Mona Alluwaym, James C. A. Main, and Sven Schewe

Thursday, 16h10-17h25 in 1A: Best paper awards

16h10 Algorithmic Information Bounds for Distances and Orthogonal Projections

Peter Cholak, Marianna Csörnyei, Neil Lutz, Patrick Lutz, Elvira Mayordomo, and Donald Stull

16h35 Testing Equivalence to the Hamiltonian Cycle Polynomial

Agrim Dewan

17h00 A Complete Equational Presentation of Qudit Circuits via Polycontrolled PROPs

Colin Blake

Friday, 9h00-10h00 in 1A: Invited speaker 5

9h00 Diagrammatic reasoning, formally

Damien Pous [+]

Abstract: Modern proof assistants make it possible to verify theorems, but often makes it harder than with pen and paper. This is especially true in domains where proofs are best depicted using diagrams. For instance, confluence diagrams in rewriting theory, commuting diagrams in category theory, or string diagrams in monoidal categories.

By using various tools and techniques to solve well-defined classes of goals, infer appropriate data, or perform high-level reasoning steps, I will show how to obtain robust and elegant proof scripts in these application domains.

Friday, 10h30-12h10 in 1A: Processes on graphs

10h30 Online Firefighting on Cactus Graphs

Bob Krekelberg, Hsiang-Hsuan Liu, and Max Hugen

10h55 Flood-It with Jewelry -- Characterizing the Game Complexity for Cograph Generalizations

Martin Darmüntzel, Christian Rosenke, and Mark Scheibner

11h20 Burning Graph Powers and Branching Trees

Jesper Jansson, Shashanka Kulamarva, Yukihiro Murakami, and Nikolaas Verhulst

11h45 Fast Rational Search via Stern-Brocot Tree

Connor Weyers, and N. V. Vinodchandran

Friday, 10h30-12h10 in 4C: Logic and verification

10h30 A Forward-Only Construction of Semilinear Inductive Invariants for VAS

Clotilde Bizière, Jérôme Leroux, and Grégoire Sutre

10h55 Deciding the Common Fragment of CTL + Past and LTL

Angelo Matteo, Massimo Benerecetti, Dario Della Monica, Fabio Mogavero, and Gabriele Puppis

11h20 Logics for Context-free Hyperproperties

Sarah Winter, and Martin Zimmermann

11h45 The Entailment Problem for Separation Logic with Overlaid Structures

Lucas Bueri, Nicolas Peltier, Quentin Petitjean, and Mihaela Sighireanu

Friday, 14h00-15h40 in 1A: Fixed-parameter tractability

14h00 Bi-criteria Approximations for Vertex Deletion Problems and d-Hitting Set

Soumen Mandal, Ashutosh Rai, and Saket Saurabh

14h25 Kernelization Bounds for Constrained Coloring

Ishay Haviv

14h50 Structural parameterizations of Geodetic Set on directed (acyclic) graphs

Laurent Beaudou, Florent Foucaud, Lucas Lorieau, and Prafullkumar Tale

15h15 Setwise Distinguishable Permutations

Ishay Haviv

Friday, 14h00-15h40 in 4C: Finite-state dimension

14h00 Regular Grammars as Effective Representations of Recognizable Sets of Series-Parallel Graphs

Radu Iosif, Marius Bozga, and Florian Zuleger

14h25 Multi-Head Finite-State Dimension

Xiang Huang, Xiaoyuan Li, Jack H. Lutz, and Neil Lutz

14h50 Finite-State Dimension for Continued Fractions: Betting, Entropy and Normality

Satyadev Nandakumar, Subin Pulari, and Akhil S

15h15 Finite-State Dimension and The Davenport-Erdős Theorem

Joe Clanin, and Matthew Rayman