2025Activity​​​‌ reportProject-TeamMOCQUA

7.1.1 FiatLux

• Keywords:
  Cellular​​ automaton, Multi-agent, Distributed systems,​​​‌ Numerical simulations
• Scientific Description:‌
  FiatLux is a discrete‌​‌ dynamical systems simulator that​​ allows the user to​​​‌ experiment with various models‌ and to perturb them.‌​‌ It includes 1D and​​​‌ 2D cellular automata, moving​ agents, interacting particle systems,​‌ etc. Its main feature​​ is to allow users​​​‌ to change the type​ of updating, for example​‌ from a deterministic parallel​​ updating to an asynchronous​​​‌ random updating. FiatLux has​ a Graphical User Interface​‌ and can also be​​ launched in a batch​​​‌ mode for the experiments​ that require statistics.
• Functional​‌ Description:
  FiatLux is a​​ cellular automata simulator in​​​‌ Java specially designed for​ the study of the​‌ robustness of the models.​​ Its main distinctive features​​​‌ are to allow users​ to perturb the updating​‌ of the system (synchrony​​ rate) and the topology​​​‌ of the grid.
• URL:​
  https://­project.­inria.­fr/­fiatlux/
• Contact:
  Nazim Fates​‌
• Participant:
  an anonymous participant​​
• Partners:
  ENS Lyon, Université​​​‌ de Lorraine

8.1.1​​ Quantum Circuits and Graphical​​​‌ Languages for Quantum Computing​

The quantum circuit model​‌ is the most standard​​ model of quantum computing.​​​‌ Quantum circuits are ubiquitous​ in quantum computing, serving​‌ as both a low-level​​ language and, surprisingly, a​​​‌ higher-level language used to​ describe certain quantum algorithms.​‌

Completeness for Quantum Circuits.​​ With the current advances​​​‌ in quantum technologies and​ quantum software, it is​‌ essential to develop formalisms​​ for transforming and reasoning​​​‌ about quantum circuits. This​ is crucial for optimizing​‌ their size or depth,​​ adapting code to architectural​​​‌ constraints, making it fault-tolerant,​ or verifying the equivalence​‌ of two circuits.

To​​ achieve these goals, quantum​​​‌ circuits can be equipped​ with equational theories that​‌ enable the transformation of​​ circuits using rules that​​​‌ are preferably simple and​ intuitive. These rules allow​‌ the replacement of a​​ circuit fragment with an​​​‌ equivalent circuit. An equational​ theory is considered complete​‌ when, for any pair​​ of circuits representing the​​​‌ same quantum evolution, there​ is a way to​‌ transform one into the​​ other using only the​​​‌ rules of the equational​ theory.

We have recently​‌ introduced the first complete​​ equational theory for quantum​​​‌ circuits 86, solving​ a problem that had​‌ been open for more​​ than 30 years. Previously,​​​‌ only certain fragments equipped​ with a complete equational​‌ theory were known, but​​ these fragments were non-universal​​​‌ and efficiently classically simulatable​ 96, 81,​‌ 82, 94.​​

In our work, we​​​‌ introduced a minimal equational​ theory for quantum circuits​‌ and proved its minimality,​​ i.e., each rule is​​​‌ necessary to ensure completeness​ 85. We also​‌ showed that any complete​​ equational theory must contain​​​‌ an unbounded family of​ equations. More specifically, for​‌ any number of qubits,​​ there exists a particular​​ equation involving that number​​​‌ of qubits which cannot‌ be derived from equations‌​‌ acting on a strictly​​ smaller number of qubits​​​‌ 85. This unexpected‌ result reveals a fundamental‌​‌ property of quantum circuits.​​

This year, we have​​​‌ introduced a new formalism‌ for quantum circuits, called‌​‌ controlled props 88,​​ which will be presented​​​‌ at FoSSaCs 2026. A‌ quantum circuit can be‌​‌ defined in terms of​​ generators composed sequentially and​​​‌ in parallel—forming, from a‌ category-theoretic perspective, a prop.‌​‌ We extended this concept​​ by introducing controlled props,​​​‌ which include an additional‌ constructor: the control. For‌​‌ any given circuit, one​​ can define a controlled​​​‌ version of it.

We‌ proposed a simple axiomatisation‌​‌ of controlled props with​​ three main objectives. First,​​​‌ to formalise the notion‌ of quantum control, which‌​‌ is currently a very​​ important topic in the​​​‌ development of quantum computing.‌ Second, to use control‌​‌ as a constructor as​​ a natural way to​​​‌ avoid the need for‌ an unbounded number of‌​‌ axioms; indeed, we proved​​ that quantum circuits described​​​‌ within this formalism admit‌ simple, bounded and intuitive‌​‌ axiomatisations. Finally, since control​​ is already used as​​​‌ a constructor in several‌ quantum programming languages, such‌​‌ as Quipper, the use​​ of controlled props facilitates​​​‌ the compilation of these‌ languages into quantum circuits.‌​‌

8.1.2 Graph states and​​ Measurement-based quantum computing

There​​​‌ are various models of‌ quantum computation. Whereas unitary‌​‌ evolutions are at the​​ heart of the standard​​​‌ model of quantum computing,‌ measurement-based quantum computing (MBQC)‌​‌ is an alternative model​​ introduced more than 20​​​‌ years ago, which consists‌ in performing quantum measurements‌​‌ over a large entangled​​ initial resource called a​​​‌ graph state. This‌ year, we solved an‌​‌ open problem concerning the​​ graphical characterization of entanglement​​​‌ in graph states, contributed‌ to advancements in measurement-based‌​‌ quantum computing (MBQC), and​​ made progress on a​​​‌ recent graph-state-based protocol called‌ $k$-parability, which serves‌​‌ as a primitive for​​ distributed quantum computing.

Graphical​​​‌ characterisation of entanglement graph‌ states. Two graph states‌​‌ have the same entanglement​​ if they can be​​​‌ transformed in each other‌ by means of local‌​‌ unitary transformations. Whereas it​​ is well known that​​​‌ local complementation, preserve entanglement,‌ the converse is however‌​‌ not true: in 2007​​ 91 an example of​​​‌ two graphs that represent‌ the same entanglement but‌​‌ cannot be transformed into​​ each other by means​​​‌ of local complementations has‌ been pointing out, leaving‌​‌ as an open question​​ a graphical characterisation of​​​‌ entanglement for graph states‌ . We have introduced‌​‌ this year a generalisation​​ of local complementation that​​​‌ captures the entanglement of‌ graph states 48.‌​‌ This result has been​​​‌ accepted at STAC 2025​ and presented at QIP​‌ 2025, the main conference​​ in quantum computing. This​​​‌ graphical characterisation of entanglement​ is strongly based on​‌ a particular graph structure​​ called minimal local set​​​‌ cover for which we​ have introduced an efficient​‌ algorithm this year, presented​​ at WG'24 as a​​​‌ purely graph theory result​ 84. Notice that​‌ our algorithm for minimal​​ local set cover has​​​‌ been used recently by​ Adam Burchardt, Jarn de​‌ Jong, Lina Vandré for​​ introducing an algorithm for​​​‌ deciding the entanglement equivalence​ of graph states 83​‌.

However, the complexity​​ of this algorithm remained​​​‌ unknown, as it depends​ on two parameters: the​‌ size of a minimal​​ local set cover and​​​‌ the complexity of solving​ linear systems that may​‌ involve an exponentially large​​ number of equations. We​​​‌ proposed an alternative algorithm​ that we proved to​‌ run in quasi-polynomial time​​ $O\left(n^{ln‌n}\right)$ to decide​ whether two graphs of​‌ order $n$ are related​​ by generalized local complementation,​​​‌ or, equivalently, whether two​ graph states (or more​‌ generally, stabilizer states) are​​ LU-equivalent. To achieve this,​​​‌ we proved that any​ graph can be covered​‌ by a polynomial number​​ of minimal local sets​​​‌ (which can be computed​ efficiently) and we bounded​‌ the order of the​​ generalized local complementation. This​​​‌ work has been accepted​ at ICALP 2025 57​‌.

Flow properties and​​ flow-preserving rewriting. A measurement-based​​​‌ quantum computation must satisfy​ so-called flow properties in​‌ order to be implementable​​ in a robustly deterministic​​​‌ way. It is known​ how to find flow​‌ structures in polynomial time​​ when they exist; nevertheless,​​​‌ their lengthy and complex​ definitions often hinder working​‌ with them. We simplified​​ these definitions by providing​​​‌ a new linear algebraic​ formulation of Pauli flow,​‌ the most general type​​ of flow, in terms​​​‌ of properties of two​ matrices arising from the​‌ adjacency matrix of the​​ underlying graph. Using this​​​‌ formulation, we obtained $\mathrm{𝒪}(n^3)‌$ algorithms for finding Pauli​​ flow, improving on previously-known​​​‌ algorithms; we also proved​ that these new algorithms​‌ are optimal barring progress​​ in the computational complexity​​​‌ of matrix multiplication. This​ work was done in​‌ collaboration with Piotr Mitosek​​ (University of Birmingham) 42​​​‌. The flow-finding algorithms​ have been implemented in​‌ Graphix, an open-source​​ library for working with​​​‌ measurement-based quantum computations 97​.

Building on the​‌ algebraic formulation, we explored​​ with Thomas Perez under​​​‌ which conditions new qubits​ can be inserted into​‌ a measurement-based quantum computation​​ while preserving the existence​​​‌ of different types of​ flow 47.

8.2.1​​ Quantum programming languages

This​​​‌ year we obtained several‌ results related to quantum‌​‌ programming languages and their​​ logical foundations. These contributions​​​‌ range from purely logical‌ systems and proof-theoretic techniques,‌​‌ to quantum lambda-calculi and​​ mixed-state computation, as well​​​‌ as a broader conceptual‌ synthesis.

Algebraic Extension of‌​‌ Intuitionistic Linear Logic. In​​ 36, we present​​​‌ the $L_{!}^{\mathrm{S‌}}$-calculus, an algebraic extension‌​‌ of Intuitionistic Linear Logic.​​ This calculus allows for​​​‌ linear combinations of terms,‌ providing a logical foundation‌​‌ for algebraic effects such​​ as superposition. We provide​​​‌ a categorical model for‌ the system, establishing a‌​‌ precise correspondence between syntax​​ and semantics. This work​​​‌ has been published in‌ the Journal of Logic‌​‌ and Computation.

IMALL with​​ a Mixed-State Modality. In​​​‌ 49, we introduce‌ $ℬ$-IMALL, a proof‌​‌ language for Intuitionistic Multiplicative​​ Additive Linear Logic extended​​​‌ with a modality $\mathrm{ℬ‌}$ to account for mixed-state‌​‌ quantum computation. The system​​ integrates pure and mixed​​​‌ quantum computation within a‌ single logical framework, supports‌​‌ linear combinations of terms,​​ and treats measurement as​​​‌ a definable proof construct‌ rather than a primitive‌​‌ constant. Cut-elimination is defined​​ via a composite reduction​​​‌ relation combining algebraic normalisation‌ with deterministic evaluation, and‌​‌ is shown to be​​ sound and adequate with​​​‌ respect to a categorical‌ semantics based on finite-dimensional‌​‌ Hilbert spaces and C​​${}^{*}$-algebras. We further​​​‌ show that every linear‌ map on ${ℂ}^{{\mathrm{2‌‌}}^n}$ is representable in​​ the pure fragment, illustrating​​​‌ the expressiveness of the‌ system through examples such‌​‌ as quantum teleportation and​​ the quantum switch. This​​​‌ work was published at‌ APLAS 2025.

A Quantum-Control‌​‌ Lambda-Calculus with Multiple Measurement​​ Bases. In 52,​​​‌ we introduce Lambda-SX, a‌ typed quantum lambda-calculus that‌​‌ extends the quantum-control paradigm​​ by supporting multiple measurement​​​‌ bases. The calculus refines‌ the type system of‌​‌ Lambda-S to track duplicability​​ relative to different bases,​​​‌ allowing measurements and control‌ to be expressed directly‌​‌ at the term level​​ without reducing all observations​​​‌ to the computational basis.‌ We formalise the syntax,‌​‌ typing rules, subtyping, and​​ operational semantics of the​​​‌ system, and establish key‌ meta-theoretical properties, including subject‌​‌ reduction, progress, and strong​​ normalisation of well-typed terms.​​​‌ This work was published‌ at APLAS 2025.

Proving‌​‌ Termination With CPO. In​​ 75, we investigate​​​‌ the use of the‌ computability path ordering (CPO)‌​‌ as a practical tool​​ for proving termination of​​​‌ complex cut-elimination calculi. We‌ introduce a new CPO‌​‌ rule that improves its​​ behaviour with respect to​​​‌ transitivity, reducing the need‌ to explicitly construct intermediate‌​‌ terms in termination arguments.​​ The approach is illustrated​​​‌ through a series of‌ increasingly expressive logical calculi,‌​‌ culminating in a quantum​​ extension with algebraic structure​​​‌ and non-deterministic measurement rules,‌ whose termination had previously‌​‌ only been conjectured. This​​ work was presented informally​​​‌ at HOR 2025; the‌ full draft is available‌​‌ on HAL.

Uniform Interpretation​​ of Parallelism. In 51​​​‌, we propose a‌ uniform interpretation of parallelism‌​‌ in intuitionistic logic, going​​​‌ beyond standard approaches based​ on monads and biproducts.​‌ Although not specific to​​ quantum computation, this interpretation​​​‌ provides a logical account​ of parallelism that is​‌ compatible with algebraic and​​ linear structures arising in​​​‌ quantum calculi. This work​ has been published at​‌ FSTTCS 2025.

Towards a​​ Computational Quantum Logic. Finally,​​​‌ in an invited paper​ at CiE 2025 46​‌, we provide an​​ overview of our ongoing​​​‌ research programme towards a​ computational quantum logic. We​‌ discuss the challenges and​​ recent progress in defining​​​‌ logical systems that capture​ the computational principles of​‌ quantum mechanics, and articulate​​ a unifying perspective connecting​​​‌ the results described above.​

8.2.2 Resource analysis of​‌ quantum programs

In 40​​, we have presented​​​‌ an imperative quantum programming​ language and a set​‌ of criteria that ensures​​ programs compute polynomial time​​​‌ computable functions. More formally,​ programs satisfying those criteria​‌ capture exactly the complexity​​ class fbqp, or​​​‌ capture exactly quantum functions​ computable with uniform families​‌ of polynomial quantum circuits.​​ We also present a​​​‌ compilation algorithm that takes​ such a program and​‌ for any number of​​ qubits creates a quantum​​​‌ circuit of size polynomial​ in this number of​‌ qubits. This algorithm was​​ improved in 55 where​​​‌ the compiled circuit is​ of optimal size, thus​‌ solving a problem known​​ as branch sequentialization  99​​​‌, which identifies the​ issue that the natural​‌ compilation of superposed branches​​ in a quantum algorithm​​​‌ yields a circuit of​ exponential size. This work​‌ was presented at the​​ 10th International Conference on​​​‌ Formal Structures for Computation​ and Deduction (FSCD 2025).​‌

In 54, we​​ modified the previous language​​​‌ and criteria in order​ to capture the class​‌ of polylogarithmic time quantum​​ algorithm, fbqpolylog. This​​​‌ constitutes the first characterization​ of fbqpolylog using a​‌ programming language. We also​​ show that we can​​​‌ compile those programs into​ quantum circuits of polylogarithmic​‌ depth (and polynomial size),​​ thus recovering the inclusion​​​‌ fbqpolylog $\subseteq$ qnc,​ but this inclusion is​‌ known to be strict,​​ hence showing that some​​​‌ qnc quantum functions, such​ as parity, cannot be​‌ programmed in a way​​ satisfying the new criteria.​​​‌ This work was presented​ at the Mathematical Foundations​‌ of Computer Science (MFCS​​ 2025) conference.

8.2.3 Descriptive​​​‌ complexity of topological invariants​

We have studied the​‌ problem of distinguishing topological​​ spaces with the minimal​​​‌ amount of complexity level,​ measured by descriptive set​‌ theory. In particular, they​​ have given a complete​​​‌ description at the first​ complexity level, and at​‌ the second complexity level​​ in the case of​​​‌ finite topological graphs. The​ results have been published​‌ in the Annals of​​ Pure and Applied Logic​​​‌ 27.

8.2.4 Presentations​ of topological spaces

We​‌ have studied a notion​​ of presentation of countably-based​​​‌ topological spaces. We have​ surprisingly shown that every​‌ such space has a​​ computable presentation. This work,​​​‌ already mentioned in the​ previous activity report, has​‌ just been published in​​ the Journal of Symbolic​​​‌ Logic 41.

8.2.5​ Characterization of second-order polytime​‌

We published 39 in​​ the journal Logical Methods​​ in Computer Science.​​​‌ This is an extended‌ version of a work‌​‌ published at Foundations of​​ Software Science and Computation​​​‌ Structures - 25th International‌ Conference (FoSSaCS 2022) 12‌​‌. This paper presents​​ characterizations of the class​​​‌ bff, the second-order‌ counterpart of the class‌​‌ of polynomial time computable​​ function. Those characterizations belong​​​‌ to the field of‌ implicit computational complexity and‌​‌ rely on a typed​​ programming language layered with​​​‌ simply typed terms. It‌ makes use of a‌​‌ tiering discipline, such discipline​​ have already been used​​​‌ to characterize various complexity‌ classes, thus illustrating the‌​‌ versatility of this method.​​ The result presented in​​​‌ this paper is a‌ first tractable, implicit, sound,‌​‌ and complete characterization of​​ bff, thus solving​​​‌ a problem that had‌ been open for 20‌​‌ years.

8.3.1 Cellular automata

We​​​‌ studied the stochastic combination‌ of two deterministic rules,‌​‌ called diploid cellular automata:​​ at each time step​​​‌ each cell independently applies‌ one rule with a‌​‌ given probability λ and​​ the other rule with​​​‌ probability 1 -λ. Following‌ a proposition initially made‌​‌ Roy et al., we​​ investigated the subset of​​​‌ the 168 endogamous rules,‌ that is, the diploid‌​‌ rules formed by a​​ rule and one of​​​‌ its symmetric (reflection or‌ conjugation). Even with such‌​‌ a restriction, these diploids​​ have a great diversity​​​‌ of dynamics. We studied‌ the cases where the‌​‌ average convergence time has​​ a logarithmic, linear, or​​​‌ quadratic scaling law and‌ show that this characterisation‌​‌ is useful to understand​​ the behaviour of these​​​‌ endogamous rules 53.‌

We studied the controllability‌​‌ problem for cellular automata,​​ that is, the ability​​​‌ to guide a system‌ from an initial state‌​‌ to a desired one​​ within a limited (and​​​‌ possibly minimum) time interval.‌ We examined this notion‌​‌ in the context of​​ Boolean one-dimensional cellular automata​​​‌ of finite length. Depending‌ on the local evolution‌​‌ rule, we investigated whether​​ it is possible to​​​‌ control the evolution of‌ the system by imposing‌​‌ particular values on the​​ boundary conditions. We showed​​​‌ that the control problem‌ can be formulated as‌​‌ a Boolean satisfiability (SAT)​​ problem and can thus​​​‌ be addressed using SAT‌ solvers. These observations allowed‌​‌ us to state that​​ only peripherally-linear rules are​​​‌ fully controllable, while for‌ other rules, the reachability‌​‌ ratio, that is, the​​ fraction of controllable pairs​​​‌ of initial and final‌ configurations, is vanishing when‌​‌ the system size grows​​ to infinity 28.​​​‌

During the three-month stay‌ of Anna Nenca (University‌​‌ of Gdansk, Poland) in​​​‌ the MOCQUA team, we​ investigated how SAT solvers​‌ could ease the design​​ of cellular automata with​​​‌ specific properties, for instance​ their abilities to solve​‌ the parity classification problem.​​ These first results allowed​​​‌ us to identify a​ series of interesting questions​‌ which are currently under​​ investigation.

During the Master's​​​‌ internship of Nassima Ait​ Sadi, we studied the​‌ property of self-correction in​​ cellular automata, with a​​​‌ focus on the correction​ of $k$-colorings for​‌ the most diffcult ones​​ 76, that is,​​​‌ for $k=\mathrm{3}$ and $k=\mathrm{4‌}$. A rule was​​ proposed to correct the​​​‌ three-colorings with a probability​ 1, in other words,​‌ a rule which fails​​ only on a neglectable​​​‌ subset of the initial​ configurations.

8.3.2 Enumerative combinatorics​‌ or combinatorics of partially​​ ordered sets

Enumeration of​​​‌ pattern-avoiding inversion sequences. The​ results presented here have​‌ been obtained by Benjamin​​ Testart during his PhD​​​‌ thesis (which started in​ 2022, and is planned​‌ to be defended in​​ 2026). They are concerned​​​‌ with inversion sequences, which​ are integer sequences $(‌{\sigma }_1,\cdots ,{\sigma }_n)‌$ such that $0\le {\sigma }_i<\mathrm{i‌}$ for all $1\le i\le n$.​​​‌ The study of pattern-avoiding​ inversion sequences began in​‌ two independent articles  95​​, 87, which​​​‌ solved the enumeration of​ inversion sequences avoiding a​‌ single pattern for every​​ pattern of length 3​​​‌ except the patterns 010​ and 100. The case​‌ 100 was recently solved​​ by Kotsireas, Mansour and​​​‌ Yildirim  93.

In​ his long article 44​‌ (published in 2025), Benjamin​​ solves the final case​​​‌ by making use of​ a decomposition of inversion​‌ sequences avoiding the pattern​​ 010 according to original​​​‌ parameters. The method is​ then expanded to solve​‌ the enumeration of inversion​​ sequences avoiding several pairs​​​‌ of patterns containing 010,​ most of the time​‌ solving also the enumeration​​ of some family of​​​‌ constrained words as an​ auxiliary problem. Going even​‌ further, Benjamin obtains all​​ missing enumerations for inversion​​​‌ sequences avoiding a pair​ of patterns of size​‌ 3 (17 such families​​ in total). To achieve​​​‌ this, Benjamin has used​ in original ways the​‌ (established) method of generating​​ trees in a few​​​‌ cases, and has otherwise​ used several decompositions of​‌ inversion sequences that he​​ introduced.

In the second​​​‌ (and shorter) article 45​ (also published in 2025),​‌ Benjamin focuses on proving​​ algebraicity of generating functions​​​‌ using generating trees. More​ precisely, he studies two​‌ families of inversion sequences,​​ provides a generating tree​​​‌ construction (which is original),​ and derives from it​‌ their algebraic generating function.​​ (Although one case was​​​‌ know by another approach,​ the second one was​‌ only conjectured so far.)​​ As expected in works​​​‌ of this type, the​ kernel method comes into​‌ play, but remarkably involves​​ some original aspects that​​​‌ may well be useful​ elsewhere.

In a third​‌ article in preparation, Benjamin​​ addresses a question of​​​‌ different nature regarding pattern-avoiding​ inversion sequences. Indeed, excluded​‌ patterns in this context​​ are not required to​​ be inversion sequence, and​​​‌ Benjamin examines, for any‌ excluded pattern $\rho$,‌​‌ the smallest set of​​ inversion sequences whose avoidance​​​‌ is equivalent to the‌ avoidance of $\rho$.‌​‌ Doing so, he corrects​​ an error in  93​​​‌ on an upper bound‌ for the maximal length‌​‌ of such an inversion​​ sequence.

Enumeration of pattern-avoiding​​​‌ alternating sign matrices. Permutations‌ can be described as‌​‌ square binary matrices containing​​ exactly one 1 in​​​‌ each row and each‌ column (using their classical‌​‌ permutation matrix representation). A​​ common generalization of permutations​​​‌ consists in allowing entries‌ 0, 1 and $-‌‌1$ in square matrices,​​ imposing that in each​​​‌ row (resp. column), the‌ non-zero entries alternate in‌​‌ sign and sum to​​ 1. These objects are​​​‌ called alternating sign matrices‌ (ASMs), and their study‌​‌ has been a challenging​​ topic in enumerative combinatorics​​​‌ for the past four‌ decades. However, so far,‌​‌ it seems that there​​ have been very few​​​‌ studies of pattern-avoidance in‌ ASMs, while this is‌​‌ a classical and rich​​ topic in the combinatorics​​​‌ of permutations.

Therefore, in‌ a collaborative project involving‌​‌ ASM experts and permutation​​ patterns experts , we​​​‌ have explored the topic‌ of pattern-avoiding ASMs. There‌​‌ are two different and​​ natural ways to do​​​‌ so, which resulted in‌ two articles, both published‌​‌ in 2025.

The first​​ one 35 investigates the​​​‌ notion that we name‌ key-avoidance in ASMs. Indeed,‌​‌ there is a classical​​ procedure in the ASMs​​​‌ literature, that associates to‌ each ASM a permutation,‌​‌ called its key.​​ In this work, we​​​‌ enumerate ASMs whose key‌ avoids a given set‌​‌ of permutation patterns in​​ several instances. We show​​​‌ that ASMs whose key‌ avoids 231 are permutations,‌​‌ thus the many known​​ enumerations for a set​​​‌ of permutation patterns including‌ 231 extends to ASMs.‌​‌ We furthermore enumerate by​​ the Catalan numbers ASMs​​​‌ whose key avoids both‌ 312 and 321. We‌​‌ also show ASMs whose​​ key avoids 312 are​​​‌ in bijection with the‌ gapless monotone triangles defined‌​‌ by Ayyer, Cori and​​ Gouyou-Beauchamps in 2011  78​​​‌. Thus key-avoidance generalizes‌ the notion of 312-avoidance‌​‌ studied there, answering a​​ question left open in​​​‌ their work. Finally, we‌ enumerate ASMs with a‌​‌ given key avoiding 312​​ and 321 using a​​​‌ connection to Schubert polynomials,‌ thereby deriving an interesting‌​‌ Catalan identity.

The second​​ one 31 focuses on​​​‌ another way of defining‌ avoidance of patterns in‌​‌ ASMs, by looking at​​ submatrices, and which we​​​‌ refer to as classical‌ avoidance. This has‌​‌ already appeared once in​​ the literature, in a​​​‌ paper by Johansson and‌ Linusson in 2007  92‌​‌. We completely classify​​ the asymptotic behavior of​​​‌ the number of ASMs‌ classically avoiding a single‌​‌ permutation pattern. In particular,​​ we give a uniform​​​‌ proof of an exponential‌ upper bound for the‌​‌ number of ASMs classically​​ avoiding one of twelve​​​‌ particular patterns, and a‌ super-exponential lower bound for‌​‌ all other single-pattern avoidance​​ classes. We also show​​​‌ that for any fixed‌ integer $k$, there‌​‌ is an exponential upper​​​‌ bound for the number​ of ASMs that classically​‌ avoid any single permutation​​ pattern and contain precisely​​​‌ $k$ negative ones. Finally,​ we prove that there​‌ must be at most​​ 3 negative ones in​​​‌ an ASM which classically​ avoids both 2143 and​‌ 3412, and we exactly​​ enumerate the number of​​​‌ them with precisely 3​ negative ones.

The middle​‌ order on permutations Two​​ extremely well-known partial orders​​​‌ exist on permutations of​ any given size: the​‌ Bruhat order, and the​​ weak order. In 33​​​‌, we introduce a​ third natural such partial​‌ order. Specifically, we define​​ a partial order ${\mathrm{P‌}}_n$ on permutations of​ any given size $\mathrm{n‌}$, which is the​​ image of a natural​​​‌ partial order on inversion​ sequences. We call this​‌ the “middle order”. We​​ demonstrate that the poset​​​‌ $P_n$ refines the​ weak order on permutations​‌ and admits the Bruhat​​ order as a refinement,​​​‌ justifying the terminology. These​ middle orders are distributive​‌ lattices and we establish​​ some of their combinatorial​​​‌ properties, including characterization and​ enumeration of intervals and​‌ boolean intervals (in general,​​ or of any given​​​‌ rank), and a combinatorial​ interpretation of their Euler​‌ characteristic. We further study​​ the (not so well-behaved)​​​‌ restriction of this poset​ to involutions, obtaining a​‌ simple formula for the​​ Möbius function of principal​​​‌ order ideals there.

The​ article 33 has been​‌ published in 2025, but​​ has been available as​​​‌ a preprint earlier. It​ has attracted some attention,​‌ and the notion of​​ middle order has already​​​‌ been generalized. Indeed, inspired​ by our work, L.​‌ Schwob (PhD student at​​ Marne-la-Vallée) defines generalized middle​​​‌ orders as distributive lattices​ on permutations that interpolate​‌ between the weak order​​ and the Bruhat order​​​‌ (our original middle order​ being the first one​‌ that was studied), and​​ explores the properties of​​​‌ these lattices. This is​ achieved through ideals in​‌ the root poset of​​ the symmetric group, and​​​‌ is further generalized by​ L. Schwob to other​‌ Coxeter groups.

The interval​​ poset of permutations The​​​‌ paper 30 was revised​ and published in 2025,​‌ but results from the​​ research internship of B.​​​‌ Izart in our team​ (June-September 2021), and from​‌ the visit of L.​​ Cioni to Loria (September-October​​​‌ 2021).

The goal of​ this research project was​‌ to investigate the links​​ between interval posets of​​​‌ permutations and substitution decomposition​ trees. The interval poset​‌ of a permutation is​​ the set of intervals​​​‌ of a permutation, ordered​ with respect to inclusion.​‌ It has been introduced​​ and studied in 98​​​‌. Substitution decomposition trees,​ on the other hand,​‌ are a rather classical​​ tool in the study​​​‌ of permutation classes, which​ was not used in​‌ 98.

We first​​ describe a procedure to​​​‌ obtain the interval poset​ of a permutation from​‌ its substitution decomposition tree.​​ We then give alternative​​​‌ proofs of some of​ the results in 98​‌, and we solve​​ the open problems that​​​‌ it posed (and some​ other enumerative problems) using​‌ techniques from symbolic and​​ analytic combinatorics. Finally, we​​ compute the Möbius function​​​‌ on interval posets.

We‌ note that our article‌​‌ 30 has sparkled the​​ interest for these objects​​​‌ by another group of‌ researchers  79, 80‌​‌.

8.3.3 Geometric or​​ probabilistic combinatorics

Decomposition of​​​‌ order types, with applications‌ to counting problems. This‌​‌ topic, at the interface​​ of combinatorics and discrete​​​‌ geometry, has emerged as‌ the result of a‌​‌ collaboration between several teams​​ in Nancy, and involves​​​‌ M. Bouvel, V. Feray‌ (IECL, Université de Lorraine),‌​‌ X. Goaoc (Gamble) and​​ F. Koechlin (post-doc with​​​‌ X. Goaoc and V.‌ Feray until September 2023,‌​‌ now CNRS researcher at​​ Paris 13). We have​​​‌ presented our results in‌ 2024 at the conference‌​‌ SOCG, one of the​​ main conferences in discrete​​​‌ geometry. The journal version‌ of our work has‌​‌ been published in 2025​​ 32.

In this​​​‌ work, we introduce and‌ study an original notion‌​‌ of decomposition of planar​​ point sets (or rather​​​‌ of their chirotopes, also‌ called order types) as‌​‌ trees decorated by smaller​​ chirotopes. This decomposition is​​​‌ based on the concept‌ of mutually avoiding sets,‌​‌ and adapts in some​​ sense the modular decomposition​​​‌ of graphs (or its‌ cousin the substitution decomposition‌​‌ of permutations) in the​​ world of chirotopes. We​​​‌ prove that the associated‌ tree always exists and‌​‌ is unique up to​​ some appropriate constraints. We​​​‌ also show how to‌ compute the number of‌​‌ triangulations of a chirotope​​ efficiently, starting from its​​​‌ tree and the (weighted)‌ numbers of triangulations of‌​‌ its parts.

We note​​ that our chirotope trees​​​‌ have been further investigated‌ by others; in particular,‌​‌ 90 describes an efficient​​ (polynomial) algorithm to compute​​​‌ the chirotope tree.

Record-biased‌ permutations. We worked for‌​‌ several years on the​​ study of a non-uniform​​​‌ distribution on permutations biased‌ by their number of‌​‌ records that we call​​ record-biased permutations. This​​​‌ project has come to‌ a conclusion with the‌​‌ article 34, currently​​ accepted pending minor revision.​​​‌ There, we give several‌ generative processes for record-biased‌​‌ permutations, explaining also how​​ they can be used​​​‌ to devise efficient (linear)‌ random samplers. For several‌​‌ classical permutation statistics, we​​ obtain their expectation using​​​‌ the above generative processes,‌ as well as their‌​‌ limit distributions in the​​ regime that has a​​​‌ logarithmic number of records‌ (as in the uniform‌​‌ case). Finally, increasing the​​ bias to obtain a​​​‌ regime with an expected‌ linear number of records,‌​‌ we establish the convergence​​ of record-biased permutations to​​​‌ a deterministic permuton, which‌ we fully characterize.

Scaling‌​‌ limits of families of​​ graphs and permutations. We​​​‌ report here on the‌ latest result and current‌​‌ project of a collaboration​​ with LIPN, IECL, CMAP​​​‌ and LISN. The purpose‌ of this collaboration is‌​‌ to establish limit shape​​ results for combinatorial structures​​​‌ (like permutations or graphs)‌ constrained to avoiding substructures,‌​‌ often using methods from​​ analytic combinatorics (which is​​​‌ original in the landscape‌ of the research on‌​‌ this topic). More precisely,​​ we study families of​​​‌ permutations or graphs defined‌ by the avoidance of‌​‌ substructures, and we answer​​​‌ (formally) the (informally phrased)​ question: “if we choose​‌ uniformly at random an​​ object of large size​​​‌ in the considered family,​ what does it look​‌ like?”.

In the paper​​ 29 (revised and published​​​‌ in 2025), we consider​ the three following families​‌ of graphs: distance-hereditary graphs,​​ 2-connected distance-hereditary graphs and​​​‌ 3-leaf power graphs (the​ latter two being subclasses​‌ of the first one).​​ We prove that the​​​‌ scaling limit of uniform​ random graphs in each​‌ of these families, with​​ respect to the Gromov–Prokhorov​​​‌ topology, is the famous​ Brownian Continuum Random Tree​‌ of Aldous. Although such​​ results are quite expected​​​‌ for families of graphs​ that are “almost trees”​‌ (like the ones we​​ consider), our approach to​​​‌ establish this result is​ original, relying on the​‌ split decomposition of graphs​​ (from the graph algorithms​​​‌ and graph theory literature)​ and on analytic combinatorics.​‌

Our newer project (started​​ in 2024, continued in​​​‌ 2025, and still work​ in progress) goes back​‌ to permutations. It aims​​ at building an automatic​​​‌ framework for describing limit​ shapes (precisely, limiting permutons​‌) of uniform permutations​​ in classes for which​​​‌ a specification by so-called​ proof-trees is provided. This​‌ covers in particular all​​ classes defined by the​​​‌ avoidance of any two​ patterns of size 4.​‌ This project combines two​​ recent developments. First, the​​​‌ software PermPAL developed by​ M. H. Albert, C.​‌ Bean, A. Claesson, E.​​ Nadeau, J. Pantone and​​​‌ H. Ulfarsson  77 allows​ for the automatic discovery​‌ of specifications by proof-trees​​ (defined in  77)​​​‌ for families of pattern-avoiding​ permutations, from which enumeration​‌ can (sometimes) also be​​ solved automatically, and from​​​‌ which random samplers are​ obtained. Second, and although​‌ the proof-trees encoding permutations​​ are different from the​​​‌ substitution decomposition trees we​ have often been working​‌ with in our series​​ of paper deriving limit​​​‌ shape results for permutations,​ they share the essential​‌ property that the occurrence​​ of patterns in permutations​​​‌ can be tracked on​ these trees. This allows​‌ to adapt the methodology​​ for proving limit shape​​​‌ results through analytic combinatorics​ that we have develop​‌ over the years to​​ this new context. Our​​​‌ goal is to do​ this is a way​‌ that can be automatized,​​ and perhaps integrated to​​​‌ PermPAL in the long​ term.

Scaling limits of​‌ inversion sequences, words, and​​ dimensional tables of integers.​​​‌ This new project has​ started in 2025, as​‌ part of the ANR-funded​​ project called LOUCCOUM (Large​​​‌ Objects Under Combinatorial Constraints​ and Outside Uniform Models).​‌

The starting idea is​​ to define a good​​​‌ notion to express limit​ shape results for inversion​‌ sequences (the combinatorial objects​​ are the core of​​​‌ B. Testart's PhD thesis),​ similarly to the notions​‌ of permutons for permutations,​​ or graphons for graphs,​​​‌ for instance. By now,​ it has become clear​‌ that the good notion,​​ which we have named​​​‌ “tablon”, will be an​ appropriate framework for describing​‌ not only limits of​​ inversion sequences, but also​​​‌ of other types of​ words on a possibly​‌ infinite alphabet, and even​​ more broadly of two-dimensional​​ tables of integers (hence​​​‌ the name tablon). As‌ a first result to‌​‌ witness that tablons are​​ a good notion, we​​​‌ proved that tablon limits‌ are characterized by substructure-densities,‌​‌ just like permutons and​​ graphons are. This is​​​‌ still a work in‌ progress, with one aspect‌​‌ that consists in establishing​​ the theoretical foundations for​​​‌ tablons, and another that‌ consists in obtaining (possibly‌​‌ universal) limiting tablon results.​​

8.3.4 Analysis of B2B​​​‌ exchange graphs

In Economy,‌ a major issue is‌​‌ the potential lack of​​ liquidity for settling the​​​‌ debts generated by payment‌ delays among companies. In‌​‌ collaboration with Massimo Amato​​ and Lucio Gobbi (Bocconi​​​‌ University and University of‌ Trento), we developed some‌​‌ economic and operational foundations​​ of a new method​​​‌ of financing companies’ financial‌ obligations  89. In‌​‌ our model, a network​​ funder sets an optimal​​​‌ combination of netting and‌ financing. Given a network‌​‌ of companies and their​​ respective invoices, and under​​​‌ the condition of a‌ full settlement of the‌​‌ invoices, we applied a​​ multilateral netting algorithm to​​​‌ the network, conceived as‌ an oriented multi-graph. Finding‌​‌ a set of invoices​​ which maximises the amount​​​‌ of debt reduced given‌ a quantity of loanable‌​‌ funds is an NP-complete​​ problem.

In 2025, we​​​‌ focused on improving the‌ integral debt netting algorithms‌​‌ that has been developped​​ by Joannes Guichon during​​​‌ his PhD's second year.‌ We were able to‌​‌ improve the computation time​​ by more than an​​​‌ order of magnitude while‌ maintaining nearly the same‌​‌ result quality 65,​​ 58, 70,​​​‌ 71. We also‌ added an additional layer‌​‌ of depth to the​​ algorithms by introducing the​​​‌ possibility of limiting the‌ available financing, allowing simulations‌​‌ that are closer to​​ realistic scenarios.

8.3.5 Local​​​‌ generation of tilings

During‌ the research initiation internship‌​‌ of Tom Favereau, we​​ studied the possibility of​​​‌ generating tilings in a‌ local way. We have‌​‌ proposed two definitions capturing​​ this intuition and developed​​​‌ techniques to classify tilings‌ according to these definitions.‌​‌ We have started a​​ systematic classification of small​​​‌ Wang tilesets. This work,‌ already mentioned in the‌​‌ previous actvity report, has​​ been published in Ergodic​​​‌ Theory and Dynamical Systems‌ 37.

8.3.6 Links‌​‌ between computational models and​​ statistical physics

Léo Gayral​​​‌ made progress on a‌ project ongoing since their‌​‌ PhD, regarding the emergence​​ of chaotic behaviours in​​​‌ statistical physics models induced‌ by finite-range interactions, themselves‌​‌ deeply tied to the​​ combinatorial structure of Subshifts​​​‌ of Finite Type, both‌ at their local and‌​‌ global scale. In particular,​​ by embedding Turing machines​​​‌ into the tilings, thus‌ by twisting the combinatorial‌​‌ properties of the SFTs,​​ one can establish links​​​‌ between (non)-computable properties of‌ Turing machines and analytical‌​‌ properties of the corresponding​​ statistical physics models.

In​​​‌ the original article, that‌ finally got published in‌​‌ Nonlinearity 38, we​​ proved a realisation result​​​‌ for any ${\Pi }_{\mathrm{2‌}}$-computable set of Ground‌​‌ States, completed by a​​ ${\Pi }_2$ upper bound​​​‌ for a broader class‌ of models. In a‌​‌ new work 68 currently​​​‌ submitted for publication, by​ expanding the previously used​‌ embedding of Turing machines,​​ we establish the existence​​​‌ of a family of​ models for which the​‌ set of Ground States​​ is highly non-robust under​​​‌ finite-range perturbations of the​ potential function.

A new​‌ ongoing project has branched​​ from these ideas, in​​​‌ collaboration with Mathieu Hoyrup​ , regarding computability properties​‌ for the maximising measures​​ in the field of​​​‌ Ergodic Optimisation, and should​ hopefully lead to new​‌ results next year.

8.3.7​​ Topological invariants of tiling​​​‌ spaces

In the study​ of tilings, we may​‌ encounter tilesets that appear​​ visually similar but yield​​​‌ wildly different combinatorial structures​ for the sets of​‌ admissible tilings. The converse​​ also holds: some tilesets​​​‌ may appear dissimilar but​ give rise to isomorphic​‌ sets of admissible tilings.​​ A common solution to​​​‌ that problem is to​ import invariants from algebraic​‌ topology (cohomology, fundamental groups,​​ etc.) and to apply​​​‌ them to sets of​ tilings. This requires endowing​‌ sets of tilings with​​ a topology. We have​​​‌ proven that the usual​ topology utilized for this​‌ purpose is in fact​​ equivalent to the well-known​​​‌ compact-open topology, and also​ to the very convenient​‌ point-open topology. Stating that​​ equivalence has required to​​​‌ fully rework the formal​ definition of what a​‌ “tiling” even is and​​ to redevelop the whole​​​‌ theory from that new​ definition. We used this​‌ equivalence to obtain a​​ full characterization of the​​​‌ compact topological spaces, which​ slightly differs from the​‌ expected one but only​​ for technical reasons. Finally​​​‌ we made significant progress​ on various cohomological calculations​‌ which were not possible​​ to do with the​​​‌ old definitions.

10.1.1 Participation in​‌ other International Programs

10.2.1‌​‌ Visits of international scientists​​

10.2.2​ Visits to international teams​‌

10.3.1 Horizon​​ Europe

10.3.2 H2020 projects‌

10.4.1 ANR

10.4.2 Other initiatives‌

11.1.1​​ Scientific events: organisation

11.1.2 Scientific events:​​ selection

11.1.3 Journal

11.1.4 Invited talks

• Miriam​​​‌ Backens gave:
  • an invited‌ talk at the 2nd‌​‌ FoQaCIA workshop (Braga, Portugal)​​
  • an invited tutorial at​​​‌ the École Jeunes Cherchereuses‌ en Informatique Fondamentale et‌​‌ ses Mathématiques (Caen, France)​​
  • an invited tutorial and​​​‌ talk at the Journées‌ 2025 du GT Scalp‌​‌ (Paris, France)
  • an invited​​ tutorial at the 1st​​​‌ QCOMICAL School on Quantum‌ and Classical Programming Languages‌​‌ and Semantics (Nancy, France)​​
• Alejandro Díaz-Caro gave:
  • an​​​‌ invited talk at the‌ special session on quantum‌​‌ computing at Computing in​​ Europe 2025
  • an invited​​​‌ talk at the XIV‌ Conference on Quantum Foundations:‌​‌ From Foundations to Quantum​​ Computing - Celebrating IYQ2025​​​‌ (CQF 2025)
  • an invited‌ talk at the ASQ3:‌​‌ Algorithms and Software Quests​​ in Quantum Qomputing
  • an​​​‌ invited talk at the‌ XIV Workshop on Philosophical‌​‌ Logic
  • an invited talk​​ at the Argentinian Symposium​​​‌ on Quantum Computing at‌ 54JAIIO
• Simon Forest gave‌​‌ an invited talk at​​ the Advances in Interactive​​​‌ and Quantitative Semantics workshop‌ (Marseille, France)
• Emmanuel Hainry‌​‌ gave an invited talk​​ at the IRN CloVe​​​‌ Workshop on Computational Complexity‌ (Copenhagen, Denmark)
• Mathieu Hoyrup‌​‌ gave an invited talk​​ at the Online Logic​​​‌ Seminar and the Cross-Alps‌ Logic Seminar
• Simon Perdrix‌​‌ gave
  • an invited talk​​ at the special session​​​‌ on quantum computing at‌ Computing in Europe 2025‌​‌
  • an invited talk at​​ Quantazur days (Nice, France)​​​‌
  • an invited talk at‌ Séminaire Les Rendez-vous de‌​‌ l'informatique, organised by​​ MENESR.
  • an invited tutorial​​​‌ at the 1st QCOMICAL‌ School on Quantum and‌​‌ Classical Programming Languages and​​ Semantics (Nancy, France)

11.1.5​​​‌ Leadership within the scientific‌ community

• Miriam Backens ,‌​‌ Mathilde Bouvel and Léo​​ Gayral are members of​​​‌ the Comité PÉDI (Parité,‌ Équité, Diversité, Inclusion) of‌​‌ the GDR IFM. Léo​​ Gayral is also webmaster​​​‌ for this committee.
• Mathilde‌ Bouvel : member of‌​‌ the steering committee of​​ the conference series Permutation​​​‌ Patterns
• Nazim Fatès :‌ chair of the IFIP‌​‌ WG1.5 on Cellular Automata​​ and Discrete Complex Systems​​​‌, member of the‌ steering committee of AUTOMATA‌​‌ 2025.
• Romain Péchoux was​​ vice-chair of the MSCA​​​‌ Fellowshing program, European Research‌ Agency, 2025.
• Simon Perdrix‌​‌ : co-head of the​​ groupe de travail Informatique​​​‌ Quantique at GdR IFM.‌

11.1.6 Scientific expertise

• Mathilde‌​‌ Bouvel served as external​​​‌ evaluator for a conference​ proposal at the Banff​‌ conference center (Canada)
• Emmanuel​​ Hainry was member of​​​‌ a CoS for a​ MCF position, Université de​‌ Lorraine, 2025.
• Emmanuel Jeandel​​ : member of the​​​‌ scientific counsel of GDR​ IFM
• Romain Péchoux was​‌ member of:
  • a CoS​​ for a CPJ, Université​​​‌ Paris Saclay, 2025.
  • a​ CoS for a Full​‌ Professor position, University of​​ Innsbruck, 2025.
• Simon Perdrix​​​‌ was member of:
  • a​ CoS for a CPJ,​‌ Université de Bordeaux, 2025.​​
  • of the Jury Inria​​​‌ CRCN / ISFP, Grenoble,​ 2025.

11.2.1 Supervision​​​‌

• Miriam Backens supervised the​ PhD of Tommy McElvanney​‌ at University of Birmingham​​ (5th year, defended February​​​‌ 25th, 2025).
• Miriam Backens​ supervised the PhD of​‌ Piotr Mitosek at University​​ of Birmingham (4th year,​​​‌ defended July 21st, 2025).​
• Miriam Backens supervised the​‌ internship of Jules Dupont​​ (École des Mines Nancy,​​​‌ until June 2025).
• Miriam​ Backens is supervising the​‌ internship of Victor Gasse​​ (École des Mines Nancy).​​​‌
• Mathilde Bouvel and Emmanuel​ Jeandel are supervising the​‌ PhD of Benjamin Testart​​ (4th year).
• Alejandro Díaz-Caro​​​‌ is supervising the PhD​ of Malena Ivnisky (4th​‌ year) at Universidad de​​ Buenos Aires.
• Alejandro Díaz-Caro​​​‌ is supervising the PhD​ of Cristian Sottile (5th​‌ year) at Universidad de​​ Buenos Aires.
• Alejandro Díaz-Caro​​​‌ is supervising the PhD​ of Rafael Romero (5th​‌ year) at Universidad de​​ Buenos Aires.
• Alejandro Díaz-Caro​​​‌ is supervising the Master​ of Science of Nicolás​‌ Monzón (2nd year) at​​ Universidad de la República.​​​‌
• Nazim Fatès is supervising​ the PhD of Joannès​‌ Guichon (4th year) with​​ Sylvain Contassot-Vivier (LORIA).
• Nazim​​​‌ Fatès has supervised the​ Master 2 internship of​‌ Nassima Ait Sadi.
• Simon​​ Forest and Pierre Clairambault​​​‌ (LIS, Marseille) and Raphaëlle​ Crubillé (LIS, Marseille) are​‌ supervising the PhD of​​ Victor Blanchi (2nd year).​​
• Mathieu Hoyrup and Guilhem​​​‌ Gamard are supervising the‌ PhD of Alexis Terrassin‌​‌ (2nd year).
• Guilhem Gamard​​ supervised the masters “long​​​‌ projects” (similar to internships)‌ of Ahmed Imed Eddine‌​‌ Kheddim and that of​​ Youva Amiar and Djedjiga​​​‌ Ait Slimani.
• Mathieu Hoyrup‌ and Benjamin Hellouin (LISN)‌​‌ are supervising the PhD​​ of Rémi Pallen (2nd​​​‌ year).
• Emmanuel Jeandel and‌ Léo Gayral are supervising‌​‌ the PhD of Vivien​​ Ducros (1st year).
• Emmanuel​​​‌ Jeandel and Julien Provilard‌ are supervising the PhD‌​‌ of Théo Joffroy (1st​​ year).
• Emmanuel Jeandel and​​​‌ Christophe Vuillot are supervising‌ the PhD of Alexandre‌​‌ Guernut (4th year, defended​​ Mai 13 2025).
• Emmanuel​​​‌ Jeandel supervised the masters‌ internship of Vivien Ducros‌​‌ and Theo Joffroy (until​​ aug 2025).
• Romain Péchoux​​​‌ and Christophe Chareton (Research‌ Engineer, CEA) are supervising‌​‌ the PhD of Jad​​ Issa (2nd year).
• Romain​​​‌ Péchoux and Simon Perdrix‌ are supervising the PhD‌​‌ of Kathleen Barsse (2nd​​ year).
• Romain Péchoux and​​​‌ Vladimir Zamdzhiev (ISFP, Inria‌ Paris-Saclay) are supervising the‌​‌ PhD of Kinnari Dave​​ (3rd year, defended December​​​‌ 17th 2025).
• Romain Péchoux‌ and Emmanuel Hainry are‌​‌ supervising the PhD of​​ Thomas Vinet (2nd year).​​​‌
• Romain Péchoux and Emmanuel‌ Hainry are supervising the‌​‌ PhD of Mario Silva​​ (4th year, defended July​​​‌ 7th 2025).
• Simon Perdrix‌ is supervising the PhD‌​‌ of Noé Delorme (3rd​​ year).
• Simon Perdrix and​​​‌ Miriam Backens are supervising‌ the PhD of Colin‌​‌ Blake (2nd year).
• Simon​​ Perdrix and Mathilde Bouvel​​​‌ supervised the PhD of‌ Nathan Claudet (3rd year,‌​‌ defended November 17th 2025).​​
• Simon Perdrix and Titouan​​​‌ Carette are supervising the‌ PhD of Thomas Perez‌​‌ (2nd year).

11.2.2 Juries​​

• Miriam Backens :
  • was​​​‌ a member of the‌ jury for the PhD‌​‌ of Nicolas Heurtel, Université​​ Paris-Saclay, defended on June​​​‌ 11th, 2025.
  • was external‌ examiner for the program‌​‌ Master in Mathematics and​​ Foundations of Computer Science​​​‌, University of Oxford,‌ UK.
• Mathieu Hoyrup was‌​‌ rapporteur of the PhD​​ of Ahmed Mimouni, Université​​​‌ Paris-Créteil, defended on October‌ 24th 2025.
• Emmanuel Jeandel‌​‌ :
  • was rapporteur of​​ the HDR of Sébastien​​​‌ Labbé, Université de Bordeaux,‌ defended June 4 2025.‌​‌
  • was a member of​​ the jury of HDR​​​‌ of Pierre-Jean Spaenlehauer, Université‌ de Lorraine, defended February‌​‌ 2 2025.
  • was rapporteur​​ of the PhD of​​​‌ Nicolas Heurtel, Université Paris-Saclay,‌ defended June 11 2025.‌​‌
• Romain Péchoux :
  • was​​ rapporteur of the PhD​​​‌ of Andrea Colledan, Universita‌ di Bologna, defended the‌​‌ April 9th 2025.
  • was​​ rapporteur of the PhD​​​‌ of Adriano Barile, Universita‌ di Torino, defended the‌​‌ September 19th 2025.
• Mathilde​​ Bouvel was a member​​​‌ of the jury for‌ the PhD of Solal‌​‌ Gaudin, Université Lyon 1,​​ defended on September 22nd,​​​‌ 2025.
• Simon Perdrix :‌
  • was external examiner for‌​‌ DPhil (PhD) of Lia​​ Yeh, Oxford University, October​​​‌ 28th, 2025.
  • was member‌ of the PhD of‌​‌ Pierre Botteron, Université de​​ Toulouse, July 9th, 2025.​​​‌
  • was member of the‌ PhD of Colm Helleher,‌​‌ Université de Bourgogne Europe,​​ October 2nd, 2025.

11.2.3​​​‌ Educational and pedagogical outreach‌

• Miriam Backens gave a‌​‌ presentation about their research​​​‌ to high-school students and​ undergraduates at the online​‌ school BeyondQuantum: Introduction to​​ Quantum and Research on​​​‌ May 12th, 2025.
• Miriam​ Backens and Kostia Chardonnet​‌ contributed the chapter “L'informatique​​ quantique et le ZX”​​​‌ 60 to the book​ Informatique fondamentale et ses​‌ Mathématiques : Une photographie​​ en 202559.​​​‌
• Mathilde Bouvel made a​ short presentation of her​‌ research to first-year students​​ of the Ecole des​​​‌ Mines de Nancy,​ on December 16th, 2025.​‌
• Alejandro Díaz-Caro gave a​​ short presentation of his​​​‌ research at the Summer​ School on “Mathematical Aspects​‌ of Quantum Information”,​​ at Institut Pascal,​​​‌ Université Paris-Saclay in June​ 2025.

11.3.1​‌ Specific official responsibilities in​​ science outreach structures

• Alejandro​​​‌ Díaz-Caro : member of​ the steering committee of​‌ the yearly winter school​​ Escuela de Ciencias Informáticas​​​‌ (Universidad de Buenos Aires)​

11.3.2 Productions (articles, videos,​‌ podcasts, serious games, ...)​​

• Interview (in Spanish) about​​​‌ quantum computing. Alejandro Díaz-Caro​ . EstudioTech YouTube channel​‌. May 10, 2025.​​
• Minicourse via Instagram (in​​​‌ Spanish) “Qué son los​ algoritmos cuánticos”. Alejandro​‌ Díaz-Caro . Fundación Sociedades​​ Digitales. November 5,​​​‌ 2025.
• Nazim Fatès :​ Remembering and Celebrating the​‌ Life of Kenichi Morita​​, contribution on reversible​​​‌ computing, remebrance day in​ honour of Pr Morita.​‌

11.3.3 Participation in Live​​ events

• Live debate (in​​​‌ Spanish) “Computación Cuántica: Debate​ de especialistas”. Alejandro​‌ Díaz-Caro . Fundación Sociedades​​ Digitales YouTube channel.​​​‌ November 21, 2025.
• Nazim​ Fatès :
  • “Peut-on faire​‌ confiance à l’intelligence-artificielle ?”,​​ Colloque du lycée Saint-Sigisbert,​​​‌ Nancy, February 6, 2025.​
  • Talk on artificial intelligence​‌ for the lycée Vatelot​​ in Toul: “Ecce​​​‌ robot : remarques sur​ la question de l’intelligence-artificielle”,​‌ March 7, 2025.
  • Wide-audience​​ talk on the theme​​​‌ “Aux sources de l'intelligence-artificielle​ – Quelques repères avant,​‌ pendant et après le​​ siècle de Descartes”, Forum​​​‌ IRTS, Nancy, April 24,​ 2025.
  • Animation of a​‌ three-hour talk and debate​​ with Erasmus+ students from​​​‌ Europe and North Africa,​ AMSED association, Strasbourg,​‌ July 24, 2025.

International journals

• 27 article​​D. E.Djamel Eddine​​​‌ Amir and M.Mathieu​ Hoyrup. Descriptive complexity​‌ of topological invariants.​​Annals of Pure and​​​‌ Applied Logic1768​September 2025, 103611​‌HALDOIback to​​ text
• 28 articleF.​​​‌Franco Bagnoli, S.​Sara Dridi and N.​‌Nazim Fatès. Regional​​ Controllability of Cellular Automata​​ as a SAT Problem​​​‌.Natural Computing25‌12026, 2‌​‌In press. HALDOI​​back to text
• 29​​​‌ articleF.Frédérique Bassino‌, M.Mathilde Bouvel‌​‌, V.Valentin Féray​​, L.Lucas Gerin​​​‌ and A.Adeline Pierrot‌. Scaling limit of‌​‌ graph classes through split​​ decomposition.The Australasian​​​‌ Journal of Combinatorics92‌3August 2025,‌​‌ 266-319HALDOIback​​ to text
• 30 article​​​‌M.Mathilde Bouvel,‌ L.Lapo Cioni and‌​‌ B.Benjamin Izart.​​ The interval posets of​​​‌ permutations seen from the‌ decomposition tree perspective.‌​‌Order42January 2025​​, 459-479HALDOI​​​‌back to textback‌ to text
• 31 article‌​‌M.Mathilde Bouvel,​​ E.Eric Egge,​​​‌ R.Rebecca Smith,‌ J.Jessica Striker and‌​‌ J.Justin Troyka.​​ Enumeration of pattern-avoiding alternating​​​‌ sign matrices: An asymptotic‌ dichotomy.Annals of‌​‌ CombinatoricsSeptember 2025.​​ In press. HALDOI​​​‌back to text
• 32‌ articleM.Mathilde Bouvel‌​‌, V.Valentin Féray​​, X.Xavier Goaoc​​​‌ and F.Florent Koechlin‌. A canonical tree‌​‌ decomposition for order types,​​ and some applications.​​​‌SIAM Journal on Discrete‌ Mathematics394October‌​‌ 2025, 2189-2241HAL​​DOIback to text​​​‌
• 33 articleM.Mathilde‌ Bouvel, L.Luca‌​‌ Ferrari and B. E.​​Bridget Eileen Tenner.​​​‌ Between weak and Bruhat:‌ the middle order on‌​‌ permutations.Graphs and​​ Combinatorics412February​​​‌ 2025, 34HAL‌DOIback to text‌​‌back to text
• 34​​ articleM.Mathilde Bouvel​​​‌, C.Cyril Nicaud‌ and C.Carine Pivoteau‌​‌. Record-biased permutations and​​ their permuton limit.​​​‌Combinatorics, Probability and Computing‌October 2025. In‌​‌ press. HALDOIback​​ to text
• 35 article​​​‌M.Mathilde Bouvel,‌ R.Rebecca Smith and‌​‌ J.Jessica Striker.​​ Key-avoidance for alternating sign​​​‌ matrices.Discrete Mathematics‌ and Theoretical Computer Science‌​‌vol. 27:1, Permutation Patterns​​ 2024Special issuesAugust​​​‌ 2024HALDOIback‌ to text
• 36 article‌​‌A.Alejandro Díaz-Caro,​​ M.Malena Ivnisky and​​​‌ O.Octavio Malherbe.‌ An Algebraic Extension of‌​‌ Intuitionistic Linear Logic: The​​ LS!-Calculus and Its Categorical​​​‌ Model.Journal of‌ Logic and Computation35‌​‌82025HALDOI​​back to text
• 37​​​‌ articleT.Tom Favereau‌ and M.Mathieu Hoyrup‌​‌. Local generation of​​ tilings.Ergodic Theory​​​‌ and Dynamical Systems45‌112025, 3377-3418‌​‌HALDOIback to​​ text
• 38 articleL.​​​‌Léo Gayral, M.‌Mathieu Sablik and S.‌​‌Siamak Taati. Characterisation​​ of the Set of​​​‌ Ground States of Uniformly‌ Chaotic Finite-Range Lattice Models‌​‌.Nonlinearity387​​June 2025, 075011​​​‌HALDOIback to‌ text
• 39 articleE.‌​‌Emmanuel Hainry, B.​​ M.Bruce M Kapron​​​‌, J.-Y.Jean-Yves Marion‌ and R.Romain Péchoux‌​‌. Complete and tractable​​ machine-independent characterizations of second-order​​​‌ polytime.Logical Methods‌ in Computer ScienceVolume‌​‌ 21, Issue 1January​​ 2025HALDOIback​​​‌ to text
• 40 article‌E.Emmanuel Hainry,‌​‌ R.Romain Péchoux and​​​‌ M.Mário Silva.​ A Polytime Quantum Programming​‌ Language.ACM Transactions​​ on Quantum Computing7​​​‌1November 2025,​ 1 - 32HAL​‌DOIback to text​​
• 41 articleM.Mathieu​​​‌ Hoyrup, A.Alexander​ Melnikov and K. M.​‌Keng Meng Ng.​​ Computable topological presentations.​​​‌The Journal of Symbolic​ Logic2025. In​‌ press. HALback to​​ text
• 42 articleP.​​​‌Piotr Mitosek and M.​Miriam Backens. An​‌ algebraic interpretation of Pauli​​ flow, leading to faster​​​‌ flow-finding algorithms.Journal​ of Physics A: Mathematical​‌ and TheoreticalDecember 2025​​HALDOIback to​​​‌ text
• 43 articleD.​Diego Ruiz, J.​‌Jérémie Guillaud, A.​​Anthony Leverrier, M.​​​‌Mazyar Mirrahimi and C.​Christophe Vuillot. LDPC-cat​‌ codes for low-overhead quantum​​ computing in 2D.​​​‌Nature Communications161​January 2025, 1040​‌HALDOI
• 44 article​​B.Benjamin Testart.​​​‌ Completing the enumeration of​ inversion sequences avoiding one​‌ or two patterns of​​ length 3.The​​​‌ Electronic Journal of Combinatorics​324November 2025​‌HALDOIback to​​ text
• 45 articleB.​​​‌Benjamin Testart. Generating​ trees growing on the​‌ left for pattern-avoiding inversion​​ sequences.Discrete Mathematics​​​‌ and Theoretical Computer Science​vol. 27:1, Permutation Patterns​‌ 2024September 2025HAL​​DOIback to text​​​‌

Invited conferences

• 46 inproceedings​A.Alejandro Díaz-Caro.​‌ Towards a Computational Quantum​​ Logic: An Overview of​​​‌ an Ongoing Research Program​.Lecture Notes in​‌ Computer Science21st Conference​​ on Computability in Europe,​​​‌ CiE 202515764Lecture​ Notes in Computer Science​‌Lisbon, PortugalSpringer Nature​​ SwitzerlandJune 2025,​​​‌ 34-46HALDOIback​ to text

International peer-reviewed​‌ conferences

• 47 inproceedingsM.​​Miriam Backens and T.​​​‌Thomas Perez. Inserting​ Planar-Measured Qubits into MBQC​‌ Patterns while Preserving Flow​​.EPTCSQPL 2025​​​‌426Varna, BulgariaAugust​ 2025, 100 -​‌ 126HALDOIback​​ to text
• 48 inproceedings​​​‌N.Nathan Claudet and​ S.Simon Perdrix.​‌ Local equivalence of stabilizer​​ states: a graphical characterisation​​​‌.STACS: 42nd International​ Symposium on Theoretical Aspects​‌ of Computer ScienceJena,​​ Germany2025HALback​​​‌ to text
• 49 inproceedings​K.Kinnari Dave,​‌ A.Alejandro Díaz-Caro and​​ V.Vladimir Zamdzhiev.​​​‌ IMALL with a Mixed-State​ Modality: A Logical Approach​‌ to Quantum Computation.​​Lecture Notes in Computer​​​‌ ScienceAPLAS 2025 -​ 23rd Asian Symposium on​‌ Programming Languages and Systems​​16201Programming Languages and​​​‌ SystemsBengaluru, IndiaSpringer​October 2025, 131-160​‌HALDOIback to​​ text
• 50 inproceedingsK.​​​‌Kinnari Dave, L.​Louis Lemonnier, R.​‌Romain Péchoux and V.​​Vladimir Zamdzhiev. Combining​​​‌ quantum and classical control:​ syntax, semantics and adequacy​‌.Foundations of Software​​ Science and Computation Structures28th​​​‌ International Conference, FoSSaCS 2025,​ Held as Part of​‌ the International Joint Conferences​​ on Theory and Practice​​​‌ of Software, ETAPS 2025​FoSSaCS 2025 - 28th​‌ International Conference on Foundations​​ of Software Science and​​​‌ Computation Structures15691Lecture​ Notes in Computer Science​‌Hamilton, CanadaSpringer Nature​​ SwitzerlandMay 2025,​​ 155-175HALDOI
• 51​​​‌ inproceedingsA.Alejandro Díaz-Caro‌ and O.Octavio Malherbe‌​‌. Beyond Monads and​​ Biproducts: A Uniform Interpretation​​​‌ of Parallelism in Intuitionistic‌ Logic.45th IARCS‌​‌ Annual Conference on Foundations​​ of Software Technology and​​​‌ Theoretical Computer Science (FSTTCS‌ 2025)45th IARCS Annual‌​‌ Conference on Foundations of​​ Software Technology and Theoretical​​​‌ Computer Science (FSTTCS 2025)‌360Leibniz International Proceedings‌​‌ in Informatics (LIPIcs)Goa,​​ IndiaSchloss Dagstuhl –​​​‌ Leibniz-Zentrum für InformatikDecember‌ 2025, 28:1-28:17HAL‌​‌DOIback to text​​
• 52 inproceedingsA.Alejandro​​​‌ Díaz-Caro and N. A.‌Nicolas A. Monzon.‌​‌ A Quantum-Control Lambda-Calculus with​​ Multiple Measurement Bases.​​​‌Lecture Notes in Computer‌ ScienceAPLAS 2025 -‌​‌ 23rd Asian Symposium on​​ Programming Languages and Systems​​​‌16201Programming Languages and‌ SystemsBengaluru, IndiaSpringer‌​‌October 2025, 151-170​​HALDOIback to​​​‌ text
• 53 inproceedingsN.‌Nazim Fatès. A‌​‌ Note on Endogamous Diploid​​ Elementary Cellular Automata.​​​‌Automata 2025 - Exploratory‌ papers and extended abstracts‌​‌Automata 2025 - 31st​​ International Workshop on Cellular​​​‌ Automata and Discrete Complex‌ SystemsAutomata 2025 -‌​‌ Exploratory papers and extended​​ abstractsLille, FranceMarch​​​‌ 2025HALback to‌ text
• 54 inproceedingsF.‌​‌Florent Ferrari, E.​​Emmanuel Hainry, R.​​​‌Romain Péchoux and M.‌Mário Silva. Quantum‌​‌ Programming in Polylogarithmic Time​​.50th International Symposium​​​‌ on Mathematical Foundations of‌ Computer Science (MFCS 2025)‌​‌Mathematical Foundations of Computer​​ Science 2025Varsovie, Poland​​​‌July 2025HALDOI‌back to text
• 55‌​‌ inproceedingsE.Emmanuel Hainry​​, R.Romain Péchoux​​​‌ and M. A.Mário‌ Alberto Machado da Silva‌​‌. Branch Sequentialization in​​ Quantum Polytime.10th​​​‌ International Conference on Formal‌ Structures for Computation and‌​‌ Deduction (FSCD 2025)FSCD​​ 2025Birmingham, United Kingdom​​​‌2025HALDOIback‌ to text

Conferences without‌​‌ proceedings

• 56 inproceedingsE.​​Eric Chitambar, K.​​​‌Kenneth Goodenough, O.‌Otfried Gühne, R.‌​‌Rose Mccarty, S.​​Simon Perdrix, V.​​​‌Vito Scarola, S.‌Shuo Sun and Q.‌​‌Quntao Zhang. Quantum​​ Graph States: Bridging Classical​​​‌ Theory and Quantum Innovation,‌ Workshop Summary.Bridging‌​‌ Classical Theory and Quantum​​ InnovationWashinghton DC, United​​​‌ StatesAugust 2025HAL‌
• 57 inproceedingsN.Nathan‌​‌ Claudet and S.Simon​​ Perdrix. Deciding Local​​​‌ Unitary Equivalence of Graph‌ States in Quasi-Polynomial Time‌​‌.52nd International Colloquium​​ on Automata, Languages, and​​​‌ Programming (ICALP 2025)52nd‌ International Colloquium on Automata,‌​‌ Languages, and Programming (ICALP​​ 2025)334Leibniz International​​​‌ Proceedings in Informatics (LIPIcs)‌Aarhus (Danemark), DenmarkSchloss‌​‌ Dagstuhl – Leibniz-Zentrum für​​ Informatik2025, 59:1-59:20​​​‌HALDOIback to‌ text
• 58 inproceedingsJ.‌​‌Joannès Guichon, S.​​Sylvain Contassot-Vivier and N.​​​‌Nazim Fatès. A‌ divide-and-conquer approach for B2B‌​‌ integral debt netting.​​Conférence 2025 du chapitre​​​‌ local de la Complex‌ Systems SocietyParis, France‌​‌June 2025HALback​​ to text

Scientific books​​​‌

• 59 bookD.Denis‌ Arzelier, M.Miriam‌​‌ Backens, K.Kostia​​ Chardonnet, P.Pierre​​​‌ Clairambault, J.Julien‌ Courtiel, M.Mioara‌​‌ Joldeş and B.Bruno​​​‌ Zanuttini. P.Pascal​ Vanier, eds. Informatique​‌ Fondamentale et ses Mathématiques​​ : Une photographie en​​​‌ 2025.Informatique Fondamentale​ et ses MathématiquesCNRS​‌ ÉditionsJune 2025HAL​​back to text

Scientific​​​‌ book chapters

• 60 inbook​M.Miriam Backens and​‌ K.Kostia Chardonnet.​​ L'informatique quantique et le​​​‌ ZX.Informatique fondamentale​ et ses Mathématiques: Une​‌ photographie en 2025June​​ 2025, 1-76HAL​​​‌back to text

Edition​ (books, proceedings, special issue​‌ of a journal)

• 61​​ proceedingsProceedings of QPL​​​‌ 2025.22nd International​ Conference on Quantum Physics​‌ and Logic (QPL 2025)​​426Varna, BulgariaEPTCS​​​‌August 2025HALDOI​

Doctoral dissertations and habilitation​‌ theses

• 62 thesisA.​​Alexandre Guernut. Fault-tolerant​​​‌ manipulation of quantum information​ with LDPC stabilizer codes​‌.Université de Lorraine​​May 2025HAL
• 63​​​‌ thesisM.Mário Silva​. Programming languages characterizing​‌ quantum efficiency.Université​​ de LorraineJuly 2025​​​‌HAL
• 64 thesisV.​Vivien Vandaele. Optimization​‌ of fault-tolerant quantum computing​​ by the ZX-calculus.​​​‌Université de LorraineJune​ 2025HAL

Reports &​‌ preprints

• 65 miscM.​​Massimo Amato, S.​​​‌Sylvain Contassot-Vivier, N.​Nazim Fatès, L.​‌Lucio Gobbi and J.​​Joannès Guichon. Reducing​​​‌ B2B Liquidity Needs With​ Integral Netting, A Systemic​‌ Solution.November 2025​​HALback to text​​​‌
• 66 miscK.Kostia​ Chardonnet, M.Marc​‌ de Visme, B.​​Benoît Valiron and R.​​​‌Renaud Vilmart. The​ Tensor-Plus Calculus.2025​‌HALDOIback to​​ text
• 67 miscK.​​​‌Kinnari Dave, L.​Louis Lemonnier, R.​‌Romain Péchoux and V.​​Vladimir Zamdzhiev. A​​​‌ programming language combining quantum​ and classical control.​‌November 2025HAL
• 68​​ miscL.Léo Gayral​​​‌ and M.Mathieu Sablik​. Non-Robustness of the​‌ Zero-Temperature-Limit Gibbs Measures to​​ Perturbations of the Potential​​​‌.July 2025HAL​DOIback to text​‌
• 69 miscJ.Joannès​​ Guichon, S.Sylvain​​​‌ Contassot-Vivier, N.Nazim​ Fatès and M.Massimo​‌ Amato. Temporal B2B​​ Debt Netting: Finite Lifespans​​​‌ and Reimbursements of the​ Financer.March 2025​‌HAL
• 70 miscJ.​​Joannès Guichon, S.​​​‌Sylvain Contassot-Vivier and N.​Nazim Fatès. Integral​‌ B2B Debt Netting: Model​​ and Static Algorithm.​​​‌February 2025HALback​ to text
• 71 misc​‌J.Joannès Guichon,​​ S.Sylvain Contassot-Vivier and​​​‌ N.Nazim Fatès.​ Optimization heuristic for large-scale​‌ B2B integral debt netting​​.November 2025HAL​​​‌back to text
• 72​ miscM.Mathieu Hoyrup​‌. Local generation of​​ languages.November 2025​​​‌HAL
• 73 miscM.​Mathieu Hoyrup. Local​‌ generation of languages: the​​ monotonic binary sequences.​​​‌January 2026HAL
• 74​ miscL.Louis Paletta​‌, A.Anthony Leverrier​​, M.Mazyar Mirrahimi​​​‌ and C.Christophe Vuillot​. High-performance local decoders​‌ for defect matching in​​ 1D.November 2025​​​‌HAL

Other scientific publications​

• 75 miscA.Alejandro​‌ Díaz-Caro, G.Gilles​​ Dowek and J.-P.Jean-Pierre​​​‌ Jouannaud. Proving Termination​ With CPO --Full Version​‌.July 2025HAL​​back to text
• 76​​ thesisN. A.Nassima​​​‌ Ait Sadi. Auto-correction‌ par automates cellulaires.‌​‌Université de lorraineNancy​​August 2025HALback​​​‌ to text