## Soutenances de thèses

Le calendrier des séances (format iCal).

Pour ajouter le calendrier des séances à votre agenda favori, souscrire au calendrier en indiquant ce lien.

### Prochaine séance

Soutenances de thèses

Vendredi 4 octobre 2024, 14 heures, Amphithéâtre Turing, Bâtiment Sophie Germain

**Klara Nosan** *Zero problems in polynomial models*

In the first part, we study identity testing for algebraic expressions involving radicals. That is, given a k-variate polynomial represented by an algebraic circuit and k real radicals, we examine the complexity of determining whether the polynomial vanishes on the radical input. We improve on the existing PSPACE bound, placing the problem in coNP assuming the Generalised Riemann Hypothesis (GRH). We further consider a restricted version of the problem, where the inputs are square roots of odd primes, showing that it can be decided in randomised polynomial time assuming GRH.

We next consider systems of polynomial equations, and study the complexity of determining whether a system of polynomials with polynomial coefficients has a solution. We present a number-theoretic approach to the problem, generalising techniques used for identity testing, showing the problem belongs to the complexity class AM assuming GRH. We discuss how the problem relates to determining the dimension of a complex variety, which is also known to belong to AM assuming GRH.

In the final part of this thesis, we turn our attention to sequences satisfying recurrences with polynomial coefficients. We study the question of whether zero is a member of a polynomially recursive sequence arising as a sum of two hypergeometric sequences. More specifically, we consider the problem for sequences where the polynomial coefficients split over the field of rationals Q. We show its relation to the values of the Gamma function evaluated at rational points, which allows to establish decidability of the problem under the assumption of the Rohrlich-Lang conjecture. We propose a different approach to the problem based on studying the prime divisors of the sequence, allowing us to establish unconditional decidability of the problem.

### Séances passées

#### Année 2024

Soutenances de thèses

Vendredi 21 juin 2024, 9 heures 30, 3052, Bâtiment Sophie Germain

**Mickaël Laurent** (IRIF, LMF) *Polymorphic type inference for dynamic languages: reconstructing types for systems combining parametric, ad-hoc, and subtyping polymorphism*

Statically typing dynamic languages poses new challenges. In particular, functions in dynamic languages can be overloaded: they can express multiple behaviors that cannot be resolved statically, but are instead selected at runtime (either by explicit type-cases or by built-in dynamic dispatch). In addition, programs typically have no (or few) type annotations. To address these problems, I present a type system that combines, in a controlled way, first-order polymorphism with intersection types, union types and subtyping, and provide an algorithm to automatically reconstruct (infer) the type of functions. This results in a type discipline in which unannotated functions are given polymorphic types (thanks to Hindley-Milner) that can capture the overloaded behavior of the functions they type (thanks to intersection types) and that are deduced by applying advanced techniques of type narrowing (thanks to union types). This makes the system a prime candidate for typing dynamic languages.

Zoom link: https://u-paris.zoom.us/j/83379216296?pwd=ZxYiEqpCprbs9leonLXgEbniPVmwXs.1

Meeting ID: 833 7921 6296

Passcode: 341938

#### Année 2023

Soutenances de thèses

Mercredi 20 décembre 2023, 14 heures, Amphithéâtre Turing, Bâtiment Sophie Germain

**Mouna Safir** (Irif) *k-Set Agreement in Distributed Systems*

In this thesis, our primary focus was on the k-set agreement problem. This problem is a generalization of the conventional consensus problem, it centers on achieving an agreement among processes, where the agreement is on at most k values, with k=1 being the consensus. The task made complex when certain processes either crash or exhibit unpredictable behavior, known as Byzantine behavior. Our objective was to clarify the conditions under which the k-set agreement can be resolved and to delineate its solvability limits.

A key achievement of this research is the comprehensive mapping of the solvability of the k-set agreement. Through new and improved algorithms, we have boosted the efficiency of k-set agreement, especially in environments characterized by Byzantine behaviors and bounded message delays, encapsulated in the Byzantine synchronous message passing system, both in authenticated and unauthenticated environment.

Although our primary focus was the Byzantine synchronous message passing system, we also explored asynchronous environments characterized by the unpredictability of message deliveries and potential process crashes. Here, we extended the solutions to address these challenges, filling gaps left by prior studies.

To summarize, our study offers an exhaustive analysis on the k-set agreement within a Byzantine Synchronous message passing system, through innovative and optimal algorithms.

Soutenances de thèses

Lundi 18 décembre 2023, 14 heures, Amphithéâtre Gouges 2, Bâtiment Olympe de Gouges

**Robin Vacus** (Irif) *Algorithmic Perspectives to Collective Natural Phenomena*

In this talk, I will present a counter-intuitive result that is reminiscent of Braess' paradox, albeit in the context of social foraging rather than network flows. Then, motivated by flocking scenarios, I will discuss the feasibility of alignment in the presence of drift noise. Finally, I will consider the self-stabilizing bit-dissemination problem, modelling the challenge of efficiently spreading information while reaching a consensus when communications are extremely constrained.

Overall, this presentation will aim to offer fresh insights into the capabilities of distributed and competitive biological systems, shedding new light on their potential and limitations.

Soutenances de thèses

Lundi 18 décembre 2023, 15 heures 30, Salle des thèses, bât Olympe de Gouges

**Maud Szusterman** (TAU, IRIF) *Contributions to algebraic complexity, extension complexity and convex geometry*

In this thesis, we propose a different model for randomised protocols, with a more flexible structure. The characterization still holds, and it additionally holds in the symmetric setting: there is a one-to-one correspondence between G-symmetric randomised protocols guessing P, and G-symmetric extensions of P. We also established an (affine) connection between two known extensions of the permutahedron (by Goemans and by Fiorini et al.), and by analogy we construct a simple extension of the regular n-gon, which turns out to be a section of the one obtained by factorization (in [FRT12]).

Two other independent works are presented in the thesis: in 2019, together with H. Fournier, G. Malod and S. Tavenas, we constructed a counter-example to a question asked by Nisan for monotone computations of non-commutative polynomials, via algebraic branching programs. Our construction also gave lower bounds for computing the elementary symmetric polynomials in the multilinear homogeneous setting. In 2018, C. Saroglou, I. Soprunov and A. Zvavitch have shown a characterization of the n-simplex as the only polytope minimizing a certain sup-ratio of mixed volumes related to the Fenchel inequality, and conjectured that the characterization holds among all convex bodies. I derived some necessary conditions on convex bodies to be minimizers, yielding a positive solution to this conjecture in R^3.

Soutenances de thèses

Jeudi 14 décembre 2023, 14 heures, Salle 3052, Bâtiment Olympe de Gouge

**Olivier Stietel** (Irif) *Local First Order Logic with Data: Toward Specification of Distributed Algorithms*

Soutenances de thèses

Jeudi 23 novembre 2023, 14 heures, Salle 580F, Halle aux Farines

**Gaëtan Douéneau-Tabot** (IRIF) *Optimization of string transducers*

Various transducer models have been defined in the literature, thanks to many features (such as non-determinism, two-wayness or nesting) which enable to increase the expressive power of the machines. In this setting, a natural question is to solve the related class membership problems: given a function computed by a transducer with “complex” features, can it be computed by a “simpler” transducer? Some of these problems have been solved in the literature, using somehow disparate proof techniques. They are generally considered as difficult. In practice, such problems can be interpreted as program optimization issues: given a program using a lot of resources, can we build a “more efficient” equivalent program?

This thesis solves various membership problems between existing classes of transductions, both over finite or infinite words. Among others, the celebrated models of two-way transducers and pebble transducers are investigated in detail. Each time, the membership procedure is non-trivial and turns out to be effective (in the sense that it builds a “simpler” transducer whenever it exists). Therefore our results can be considered as program optimization statements. Furthermore, we offer a systematic high-level strategy for solving these problems, which relies on semantic properties (i.e. dealing intrinsically with the functions) as well as syntactic properties (referring to the transducers which compute these functions).

Additionally, this thesis provides new computation models and characterizations in order to capture known classes of transductions. These results complete the previous understanding of these classes and provide new insights on their expressive power. The author believes that the various techniques of this manuscript form a rather extensive toolbox for investigating other open membership problems.

Soutenances de thèses

Mardi 31 octobre 2023, 11 heures, Salle 3052 & Zoom

**El-Amine Cherrat** (IRIF) *Quantum Algorithms for Reinforcement Learning*

Soutenances de thèses

Jeudi 14 septembre 2023, 13 heures, Amphitheatre Turing & Zoom

**Pierre Meyer** (IRIF) *Sublinear-communication secure multiparty computation*

Soutenances de thèses

Mardi 12 septembre 2023, 14 heures, Salle 127 Bâtiment Olympe de Gouges

**Aliaume Lopez** (IRIF, LMF) *First Order Preservation Theorems in Finite Model Theory: Locality, Topology and Limit Constructions*

Details can be found here: https://www.irif.fr/~alopez/posts/2023-08-23.html

Soutenances de thèses

Lundi 11 septembre 2023, 14 heures 30, Amphitheatre 10E, Halle aux Farines & Zoom

**Filippo Brunelli** (IRIF) *Algorithmic aspects of reachability in temporal graphs*

We study the problem of computing minimum cost temporal walks, where ``cost'' is to be intended in a very wide sense. Indeed, we introduce an algebraic cost structure that can be instantiated to model all the classical criteria of walk optimisation in temporal graphs such as arrival time or duration, as well as linear combination of them or lexicographic compositions. Moreover, we study this problem in temporal graphs that are subject to waiting time constraints. Our main result on this topic is a temporal-edge scanning algorithm for single-source minimum-cost walks taking as input an acyclic time-expanded representation of the temporal graph and running in linear time. We also show that the setting in which we obtain linear-time is the widest possible: an additional logarithmic factor is needed both when the acyclicity assumption is dropped, or when a weaker temporal graph representation is used.

When we speak about temporalisation we are referring to the network design problem of turning a static graph into a temporal graph while optimising a certain criteria. In particular, we study a problem inspired by the optimisation of bus/metro/tramway schedules in a public transport network where each trajectory of a vehicle is modelled by a walk in the directed graph representing the map of the network. We consider the problem of turning a collection of such walks (called trips) in a directed graph into a temporal graph by assigning a starting time to each trip so as to maximise the reachability among pairs of nodes. We obtain several complexity results. Among them, we show that maximising reachability via trip temporalisation is hard to approximate within a factor $\sqrt{n}/12$ in an $n$-vertex digraph, even if we assume that for each pair of nodes, there exists a trip temporalisation connecting them. On the positive side, we show that there must exist a trip temporalisation connecting a constant fraction of all pairs if we additionally assume symmetry, that is, when the collection of trips to be scheduled is such that, for each trip, there is a symmetric trip visiting the same nodes in reverse order. Notice that symmetry is a fair assumption in the context of public transit networks, where a bus or metro line usually consists in trips in both directions.

Soutenances de thèses

Lundi 17 juillet 2023, 14 heures, Room 027C, Halle aux Farines

**Antoine Allioux** (IRIF) *Higher Structures in Homotopy Type Theory*

In this thesis, we break this situation of circular dependency by extending type theory with a universe of cartesian polynomial monads which, crucially, satisfy their laws definitionally. This extension permits the presentation of types and their higher structures as opetopic types which are infinite collections of cells whose geometry is described by opetopes. Opetopes are geometric shapes originally introduced by Baez and Dolan in order to give a definition of n-categories. The constructors under which our universe of cartesian polynomial monads is closed allow us to define, in particular, the Baez-Dolan slice construction on which is based our definition of opetopic type.

Opetopic types then enable us to define coherent higher algebraic structures, among which infinity-groupoids and (infinity, 1)-categories. Crucially, their higher structure is univalent in that it coincides with the one induced by their identity types. We then establish some expected results in order to motivate our definitions.

Soutenances de thèses

Mercredi 28 juin 2023, 10 heures, Jacques Louis Lions 1 hall (building C of INRIA Paris)

**Simona Etinski** (IRIF) *Generalized Syndrome Decoding Problem and its Application to Post-Quantum Cryptography*

Soutenances de thèses

Vendredi 23 juin 2023, 15 heures 30, Room 147 Olympe de Gouges & Zoom

**Weiqiang Yu** (IRIF) *Signature packing and vertex partition of signed graphs and graphs*

In the first part of this thesis, we focus on signature packing problems of signed graphs. A signed graph $(G, \sigma)$ is a graph $G$ equipped with a signature $\sigma$ which assigns to each edge of $G$ a sign (either $+$ or $-$). The key concept that separates a signed graph from a 2-edge-colored graph is the notion of switching, a switching at a subset $X$ of vertices of $G$ is to multiply the signs of all edges in the edge-cut $(X, V\setminus X)$ by $-$. A signed graph $(G, \sigma')$ is said to be switching-equivalent (or simply equivalent) to $(G, \sigma)$ if it is obtained by a switching on an edge-cut. Then we define the signature packing number of a signed graph $(G, \sigma)$, denoted $\rho(G, \sigma)$, to be the maximum number of signatures $\sigma_1, \sigma_2,\cdots, \sigma_l$ such that each $\sigma_i$ is switching equivalent to $\sigma$ and the sets $E^{-}_{\sigma_i}$, negative edges of $(G,\sigma_i)$, are pairwise disjoint. We show that it is captured by specific homomorphism. Then we establish connection to several well-known problems: e.g. the four coloring problem, Seymour's edge coloring conjecture. More precisely, we first show that if $G$ is a $K_5$-minor-free bipartite simple graph, then for any signature $\sigma$ we have $\rho(G,\sigma)\geq 4$. Secondly, we continue using the language of packing number and extend the technique to verify that for any antibalanced signed planar graph $(G,\sigma)$ of negative girth at least $5$, $\rho(G,\sigma)\geq 5$. Thirdly, we study a generalization of the packing number. Instead of considering one signature and its equivalent signatures, we separate $k$ signatures which are not necessarily switching equivalent. Since there exists planar graph of packing number 1, we investigate sufficient conditions for a planar graph such that we could separate 2 or 3 signatures.

The second part of this thesis is about vertex decomposition of sparse graphs. We first study the vertex decomposition of planar graphs of girth at least $5$. It is known that every planar graph of girth at least $5$ can be vertex decomposed into two induced subgraphs, one of maximum degree at most 3, the other of maximum degree at most 5. We strengthen this result by showing that these induced subgraphs can be chosen to be forests. We then work on sparse graphs with maximum average degree condition. More precisely, we use potential method to prove that every graph $G$ of $mad(G)\leq \frac{16}{5}$ can be vertex decomposed into two forests of maximum degree at most 1 and 4. Consequently, every graph of genus at most $1$ and girth at least $6$ also admits such decomposition.

Soutenances de thèses

Mardi 20 juin 2023, 14 heures, Amphithéâtre 1A, Halles aux Farines

**Guillaume Aubian** (IRIF) *Colouring Digraphs*

Soutenances de thèses

Jeudi 13 avril 2023, 14 heures, Zoom

**Alen Đurić** *Quadratic normalisations and coherent presentations of monoids*

Soutenances de thèses

Mercredi 15 février 2023, 9 heures, Online

**Anupa Sunny** (IRIF) *Complexity measures through the lens of two-player games and signatures of the hypercube*

In the first part of this thesis, we introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game in which two players are given inputs with different function values and are asked to output some index $i$ where their inputs differ, in a zero-communication setting. We give upper and lower bounds for private coin, public coin, shared entanglement and non-signaling strategies, and give some separations.

In the second part of this thesis, we revisit the celebrated proof of the sensitivity conjecture by Hao Huang. Using spectral techniques, Huang proved that every subgraph of the hypercube Hn of dimension n induced on more than half the vertices has maximum degree at least $\sqrt{n}$. Combined with earlier work, this completed a proof of the sensitivity conjecture. We show an alternate proof of Huang’s result using only linear dependency of vectors associated with the vertices of the hypercube. Our approach helps gain insight on more structural properties of the induced subgraph in addition to the largest degree. As an application, we show that for any Boolean function $f$, the polynomial degree is bounded above by the product of 0-sensitivity and 1-sensitivity, $s_0(f)s_1(f)$, a strictly stronger statement which implies Huang’s theorem. We also obtain structural relations for induced subgraphs at distance 3.

A key implement in Huang’s proof was signed hypercubes with the property that every cycle of length 4 is assigned a negative sign. We take a detailed look at this signature and give a nearly optimal signature that uses the minimum number of negative edges while ensuring that every 4-cycle is negative. This problem turns out to be related to one of Erdős’ problems on the largest 4-cycle free subgraph of the hypercube.

Soutenances de thèses

Mercredi 25 janvier 2023, 13 heures 30, Amphithéâtre Alan Turing & Zoom

**Farzad Jafarrahmani** (IRIF) *Fixpints of Types in Linear Logic from a Curry-Howard-Lambek Perspective*

#### Année 2022

Soutenances de thèses

Jeudi 15 décembre 2022, 17 heures, Online

**Berk Cirisci** (IRIF) *Formal Verification of Concurrent Data Structures*

Soutenances de thèses

Jeudi 1 décembre 2022, 14 heures, Salle 3052 du bâtiment Sophie Germain & Zoom

**Abhishek De** (IRIF) *Linear logic with least and greatest fixed points: truth semantics, complexity, and a parallel syntax*

Manuscript

Soutenances de thèses

Vendredi 18 novembre 2022, 13 heures 30, Salle 0011 du bâtiment Sophie Germain & Zoom

**Loïc Peyrot** (IRIF) *From Proof Terms to Programs. An operational and quantitative study of intuistionistic Curry-Howard calculi*

The atomic λ-calculus and the λ-calculus with generalized applications are two (independent) variants of the λ-calculus originating in computational interpretations of proof theory. While programming languages are built from specific deterministic evaluation strategies, the existing literature on the atomic λ-calculus and generalized applications only go over the general theory of the calculi. In particular, reduction of terms is unrestricted, and only analyzed qualitatively. This induces a gap between theory and practice, which we strive to diminish in this thesis.

Starting from the atomic λ-calculus, we isolate the most salient concept of its operational semantics, that we call node replication. This is a particular substitution procedure, which duplicates terms finely, one node of the syntax tree at a time. We follow up with λ-calculi with generalized applications. They use a ternary application constructor, adding a continuation to the usual binary application. In this work, we develop the operational theories built on node replication and generalized applications separately. For the two of them: On an operational level, we give several evaluation strategies, all observationally equivalent to the corresponding strategies in the λ-calculus. On a logical level, our approach is guided by quantitative types. We provide different type systems that inductively characterize semantic properties, but also give quantitative bounds on the length of reduction and the size of normal forms.

More precisely, in the first part of this thesis, we implement node replication by means of an explicit substitution calculus. We show in particular how node replication can be used to implement full laziness, a well-known evaluation strategy for functional programming languages like Haskell. We prove observational equivalence properties relating the fully lazy semantics with the standard ones. In the second part of the thesis, we start with an operational and logical characterization of solvability in λ-calculi with generalized applications. We show how this framework gives rise to a remarkable operational theory of call-by-value. The call-by-name characterization relies on an original calculus with generalized applications. We show in both cases that the operational semantics are compatible with a quantitative model, unlike the one of the original call-by-name calculus. We then prove essential properties of this new call-by-name calculus, and show observational equivalence with the original one.

Soutenances de thèses

Jeudi 17 novembre 2022, 10 heures, 1002

**Pierre Nigron** *Effectful programs and their proofs in type theory : application to certified packet processing*

Soutenances de thèses

Lundi 7 novembre 2022, 14 heures, Université Côte d'Azur

**Mehdi Zaïdi** *Dualité pour le fragment existentiel de la logique du premier ordre sur les mots*

Soutenances de thèses

Mercredi 26 octobre 2022, 14 heures, ENS Lyon

**Harriet Walsh** *Nouvelles classes d'universalité pour les partitions aléatoires par Harriet Walsh*

Soutenances de thèses

Vendredi 21 octobre 2022, 13 heures 30, Salle des thèses (580F, halle aux farines)

**Hugo Moeneclaey** *Cubical Models Are Cofreely Parametric*

Soutenances de thèses

Jeudi 20 octobre 2022, 14 heures, 3052

**Daniel Szilagyi** *Towards efficient quantum algorithms for optimization and sampling*

Soutenances de thèses

Mardi 20 septembre 2022, 10 heures, Salle 270 F des Halles aux Farines & Zoom

**Ny Aina Andriambolamalala** (IRIF) *Decentralized communications and Beep model*

Keywords: Distributed Computing, Initialization, Naming, Optimal, Beep, Leader Election, Energy Complexity, Broadcasting, Clustering, Time Complexity, Randomized, Radio Networks, Synchronized

Soutenances de thèses

Mardi 12 juillet 2022, 9 heures 30, CEA Nano innovation bat 862 ampli 33/34

**Zenab Nehaï** (CEA-IRIF) *Formalisation et vérification des systèmes blockchain*

Soutenances de thèses

Vendredi 10 juin 2022, 12 heures, Online, zoom

**Yiting Jiang** (IRIF and ZJNU-China) *Many aspects of graph coloring*

Soutenances de thèses

Mardi 24 mai 2022, 14 heures, Salle 3052 & Zoom

**Zhouningxin Wang** (IRIF) *Circular coloring, circular flow, and homomorphism of signed graphs*

In the first part of the thesis, we extend the notion of the circular coloring of graphs to signed graphs, as a refinement of Zaslavsky's $2k$-coloring of signed graphs. We develop some tools, for example, signed circular cliques, signed bipartite circular cliques and signed indicators, to determine the circular chromatic number of signed graphs. We provide bounds on the circular chromatic number of several important classes of signed graphs: signed $d$-degenerate simple graphs, signed bipartite planar simple graphs, signed planar simple graphs, and signed simple graphs whose underlying graph is $k$-colorable with arbitrary large girth.

In the second part, as a dual notion of the circular coloring of signed graphs, we introduce the notion of circular flow in mono-directed signed graphs. This is different from the widely-studied concept of the flows on bidirected signed graphs. We adapt and extend the ideas from the theory of flows on graphs to signed graphs. We provide a series of flow index results of signed graphs with given edge-connectivity conditions. Especially, the condition of $(6p-2)$-edge-connectivity is proved to be sufficient for a signed Eulerian graph to admit a circular $\frac{4p}{2p-1}$-flow. When restricted to planar graphs, we prove a stronger result that every signed bipartite planar graph of negative-girth at least $6p-2$ is circular $\frac{4p}{2p-1}$-colorable. This is so far the best negative-girth bound of the bipartite analogue of the Jaeger-Zhang conjecture.

The focus of the third part is on the homomorphism problem of signed (bipartite) planar graphs. We first provide an improved and also tight upper bound on the circular chromatic number of signed bipartite planar simple graphs using the number of vertices as a parameter. Secondly, motivated by a reformulation of the $4$-color theorem, with the newly-developed potential method, we bound from below the edge-density of $C_{-4}$-critical signed graphs and consequently, we prove that every signed bipartite planar graph of negative-girth at least $8$ maps to $C_{\Four}$ and that this girth bound is the best possible. Thirdly, using an edge-coloring result whose proof is based on the $4$-color theorem, we show that every signed bipartite planar graph of negative-girth at least $6$ admits a homomorphism to $(K_{3,3}, M)$, which could be regarded as an analogue of the Gr\“otzsch Theorem. Last, we confirm that the condition $mad(G)< \frac{14}{5}$ is sufficient for a signed graph to admit a homomorphism to $(K_6, M)$.

#### Année 2021

Soutenances de thèses

Mercredi 15 décembre 2021, 14 heures, Amphithéatre Gouges 1 & Youtube

**Simon Mauras** (IRIF) *Analysis of Random Models for Stable Matchings*

Stable matchings have been an extensive research topic in computer science and economics. Results in the computer science literature include the lattice structure of the set of stable matchings, and algorithms to compute it. In the economics literature, researcher have studied the incentives of agents taking part in two-sided matching markets, both from the theoretical and empirical point of views.

A recent line of works study the properties of stable matchings, using stochastic models of two-sided matching markets where the preferences of agents are drawn at random. This thesis follows this direction of inquiry, and considers two main questions: “who can manipulate?” and “who gets what?”.

The first part, addressing the question “who can manipulate?”, contains three different results. In a first result (Chapter 4), we show that when one side of the market has strongly correlated preferences, incentives to manipulate are reduced. In a second result (Chapter 5), we show that uncorrelated preferences is a worst case situation when compared to correlated preferences. Proofs of both results are based on a randomized analysis of the algorithm which computes the incentives agents have to manipulate. In a third result (Chapter 6), we study the incomplete information game where students must apply to a limited number of schools, and thus report their preferences strategically. We prove the existence of symmetric equilibria and design algorithms to compute equilibria in various special cases.

The second part, addressing the question “who gets what?”, also contains three different results. In a first result (Chapter 7), we show that under a certain input distribution of preferences, the two variants of deferred acceptance produce the same output distribution on matchings. Proofs use the lattice structure of stable matchings, show that a fixed matching has the same probability of being the top or bottom element, and give a closed formula for the probability of two agents being matched. In a second result (Chapter 8), we consider a model where the probabilities that agents like each are quantified by a “popularity” matrix, and we give evidences that the probabilities that deferred acceptance matches agents is asymptotically given by the scaled matrix where lines/columns sum up to 1. In a third result (Chapter 9), we study the time complexity of deferred acceptance, which relates to the rank people from the proposing side give to their partner. Proofs are based on a reduction to the coupon collector's problem.

Soutenances de thèses

Mardi 14 décembre 2021, 10 heures, Zoom

**Mouhamad Al-Joubbeh** (IRIF) *Minimal Separators for graphs and Paths in digraphs*

Soutenances de thèses

Lundi 13 décembre 2021, 14 heures, Room Halle 027C & Zoom

**Pierre Ohlmann** (IRIF) *Monotonic graphs for parity and mean-payoff games*

The problems of determining the winner for these two games thus belong to NP X coNP, and have attracted considerable attention since the early nineties when parity games were shown equivalent to the model-checking problem for μ-calculus. Both games moreover find numerous practical application, most notably they provide adequate models for synthesis problems on reactive systems.

Despite decades of efforts toward polynomial time algorithms, it was only recently that a breakthrough was achieved in this direction by Calude, Jain, Khoussainov, Li and Stephan, who presented in early 2017 an algorithm running in quasipolynomial time for solving parity games. Quickly after, several different algorithms with similar runtime were discovered, and later unified by the separating approach proposed by Bojańczyk and Czerwiński, and identified as value iteration algorithms.

We introduce monotonic graphs for studying structural and algorithmic aspects of such in finite duration games. These natural objects have numerous (more or less) implicit occurrences in the literature.

We start by showing that the existence of universal well-ordered such graphs characterises (half ) positionality of arbitrary winning conditions. This yields a novel approach to establishing and combining such structural results.

We then advocate that (universal) monotonic graphs provide different handles for constructing algorithms. Finite monotonic graphs induce value iteration algorithms, which are shown to be roughly equivalent to Bojańczyk and zerwiński’s separating approach in general. This allows us to formulate lower bounds for mean-payoff games, and conclude that value iteration algorithms are inadequate to improve on the current state of the art. We also study value iteration algorithms for different well-known extensions of these games.

Monotonic graphs also give a generic formalisation for strategy improvement algorithms. More precisely, we establish that valuations induced by monotonic graphs are fit for strategy improvement if and only if they are positional for the opponent. This encompasses known strategy improvement frameworks, allows us to propose new algorithms and perhaps more importantly, introduces a new tool for their difficult study.

Surprisingly, monotonic graphs also find applications for symmetric algorithms, such as those based on attractors. For parity as well as mean-payoff games, we find that monotonic graphs allow us to shed light and improve on the recent state of the art.

Soutenances de thèses

Lundi 13 décembre 2021, 15 heures, Zoom

**Axel Osmond** *Une étude catégorique des dualités spectrales*

Soutenances de thèses

Jeudi 25 novembre 2021, 14 heures, Amphithéâtre Charpak, Campus Pierre et Marie Curie

**Federico Centrone** (IRIF) *Practical protocols for quantum communication networks*

The first concerns an interactive proof quantum protocol showing experimental evidence of computational quantum advantage in the interactive setting for the first time. In this scenario, we have a computationally unbounded quantum prover who wants to convince an honest verifier of the existence of a certain solution to a complex mathematical problem, by sending part of the proof in the form of quantum states. Our quantum scheme lets the verifier verify the prover's assertion without actually receiving the whole solution. We prove that if the agents were not allowed to use quantum resources, the verification protocol would require an exponential time in the size of the solution, leading to a quantum advantage in computational time that we could demonstrate in our laboratory.

The second copes with an electronic-voting protocol that exploits an untrusted multipartite entangled quantum source to carry on an election without relying on election authorities, whose result is publicly verifiable without compromising the robustness of the scheme and that can be readily implemented with state-of-the-art technology for a small number of voters. Unlike previous results, our scheme does not require simultaneous broadcasting and works also in noisy scenarios, where the security is bounded by the fidelity of the quantum state being used.

Last, we simulate many modes squeezed states as continuous variables Gaussian quantum networks with complex topologies, characterizing their correlations and estimating the scaling of their cost while the networks grow using a squeezing resource theory. We prove a result that allows us to enhance the entanglement between two nodes in the network by measuring the multiple paths linking them and we employ this effect to devise an entanglement routing protocol, whose performance is particularly effective on large complex networks.

Soutenances de thèses

Vendredi 12 novembre 2021, 14 heures, Online

**Léo Stefanesco** (IRIF) *Asynchronous and Relational Soundness Theorems for Concurrent Separation Logic*

Manuscript

Soutenances de thèses

Mardi 9 novembre 2021, 17 heures, Salle 3052 & Zoom

**Victor Lanvin** (IRIF) *A Semantic Foundation for Gradual Set-theoretic Types*

Set-theoretic types are well-suited to a semantic-based approach called “semantic subtyping”, in which types are interpreted as sets of values, and subtyping is defined as set-containment between these sets. We adopt this approach throughout the entirety of this thesis. Since set-theoretic types are characterized by their semantic properties, they can be easily embedded in existing type systems. This contrasts with gradual typing, which is an intrinsically syntactic concept since it relies on the addition of a type annotation to inform the type-checker not to perform some checks. In most of the existing literature, gradual typing is added by extending the subtyping relation in a syntactic way. This makes the approach very difficult to extend and generalize as this heavily depends on the system at hand.

In this thesis, we try and reconcile the two concepts, by proposing several semantic interpretations of gradual typing. The manuscript is divided into two parts. In the first part, we propose a new approach to integrate gradual typing in an existing static type system. The originality of this approach comes from the fact that gradual typing is added in a declarative way to the system by adding a single logical rule. As such, we do not need to revisit and modify all the existing rules. We then propose, for each declarative type system, a corresponding algorithmic type system, based on constraint solving algorithms. We illustrate this approach on two different systems. The first system is a Hindley-Milner type system without subtyping. We present a gradually-typed source language, a target language featuring dynamic type checks (or “casts”), as well as a compilation algorithm from the former to the latter. We then extend this language with set-theoretic types and subtyping on gradual set-theoretic types, and repeat this presentation.

In the second part of this manuscript, we explore a different approach to reconcile set-theoretic types and gradual typing. While the first part of the thesis can be seen as a logical approach to tackle this problem, the second part sets off along a more semantic strategy. In particular, we study whether it is possible to reconcile the interpretation of types proposed by the semantic subtyping approach and the interpretation of the terms of a language. The ultimate goal being to define a denotational semantics for a gradually-typed language. We tackle this problem in several steps. First, we define a denotational semantics for a simple lambda-calculus with set-theoretic types, based directly on the semantic subtyping approach. This highlights several problems, which we explain and fix by adapting the approach we used. We then extend this by giving a formal denotational semantics for the functional core of CDuce, a language featuring set-theoretic types and several complex constructs, such as type-cases, overloaded functions, and non-determinism. Finally, we study a gradually-typed lambda-calculus, for which we present a denotational semantics. We also give a set-theoretic interpretation of gradual types, which allow us to derive some very powerful results about the representation of gradual types.

Soutenances de thèses

Vendredi 5 novembre 2021, 14 heures, Bâtiment Sophie Germain

**Antoine Pietri** (IRIF) *Organizing the graph of public software development for large-scale mining*

Soutenances de thèses

Vendredi 22 octobre 2021, 16 heures, 3052

**Jonas Landman** (IRIF) *Quantum Algorithms for Unsupervised Machine Learning and Neural Networks*

Soutenances de thèses

Mardi 28 septembre 2021, 15 heures, Salle 3052 & Zoom

**Chaitanya Leena Subramaniam** (IRIF) *From dependent type theory to higher algebraic structures*

The second part of this dissertation concerns accessible reflective localisations of locally presentable infinity-categories. We give a definition of “pre-modulator”, and prove a canonical correspondence between pre-modulators and accessible orthogonal factorisation systems on a locally presentable infinity-category. Moreover, we show that every such factorisation system can be generated from a pre-modulator by a transfinite iteration of a “plus-construction”. We give definitions of “modulator” and “left exact modulator”, and prove that they correspond to those factorisation systems that are modalities and left-exact modalities respectively. Finally we obtain a correspondence between left-exact localisations of infinity-topoi and left-exact modulators.

Soutenances de thèses

Lundi 27 septembre 2021, 15 heures, Online via Zoom

**Zeinab Galal** (IRIF) *Bicategorical orthogonality constructions for linear logic*

Soutenances de thèses

Mercredi 7 juillet 2021, 14 heures, Salle 3052 et Zoom

**Yassine Hamoudi** (IRIF) *Quantum Algorithms for the Monte Carlo Method*

Soutenances de thèses

Mardi 29 juin 2021, 10 heures, Amphithéâtre Alan Turing & Zoom

**Rémi Nollet** (IRIF) *A study of circular representations of infinite proofs for fixed-points logics, their5expressiveness and complexity.*

Soutenances de thèses

Mardi 29 juin 2021, 14 heures, Online

**Louis Vuilleumier** *Continuous reductions on the Scott domain and decomposability conjecture*

Soutenances de thèses

Lundi 24 mai 2021, 14 heures, Bâtiment Sophie Germain

**Rachid Zennou** (IRIF) *Méthodes algorithmiques pour la vérification de la consistance dans les systèmes distribués*

Soutenances de thèses

Mardi 11 mai 2021, 15 heures, Online

**Yixin Shen** (IRIF) *Classical and quantum cryptanalysis for Euclidean lattices and subset sum*

Soutenances de thèses

Mardi 30 mars 2021, 16 heures, Online

**Nicolas Jeannerod** (IRIF) *Verification of Shell Scripts Performing File Hierarchy Transformations*

Shell is a scripting language providing control structures around Unix utility calls. Unix utilities are objects that can perform all kind of transformation on Unix filesystems. We model Unix filesystems using feature trees and transformations of Unix filesystems using formulas in a feature tree logic named FTS. We describe these modelisations extensively and discuss their validity. The control structures of Shell scripts are converted to control structures in an intermediary language that has clearly defined semantics. This involves the definition of this intermediary language, the design of a static parser for Shell scripts and of a conversion that respects the semantics of both languages. The semantics of Shell scripts is then computed using symbolic execution of the aforementioned intermediary language, using a database of specifications of Unix utility calls as formulas of FTS. The result is, for each potential trace of execution of a Shell script, a formula of FTS describing the filesystem transformation this trace performs.

The main part of the thesis then focuses on decidability of formulas of FTS. The goal is to be able to detect traces of execution of Shell scripts that cannot happen and to check properties on the Shell scripts, such as “if the script fails, then it must not have performed any transformation”. A first, theoretical, part aims at showing that the full first-order theory of FTS is decidable. This goes by first reasoning only on Σ₁-formulas of FTS and defining a system of rules R₁ that transforms Σ₁-formulas. We show that we can use R₁ to decide the satisfiability of Σ₁-formulas as well as some other properties. We then extend the reasoning from Σ₁-formulas to first-order formulas of FTS using properties of R₁ and weak quantifier eliminations. We conclude by stating that the first-order theory of FTS is indeed decidable. A second, more practical, part aims at designing efficient decision procedures for a subset of FTS rich enough to express the semantics of Unix utilities and Shell scripts. This goes by focusing on conjunctive formulas and improving on R₁. This results in a system R₂ which is more efficient on conjunctive formulas but would not have the required properties to prove decidability of the first-order. We then show how R₂ can be implemented efficiently and that it can be extended without loss of efficiency to support specific forms of Σ₁-formulas.

Finally, this thesis describes the applications of the theoretical work to the implementation of a toolchain able to analyse all software packages in the Debian distribution and report on them. We describe our analysis and the bugs that we have found during the whole project. This thesis takes place within the CoLiS project, ANR-15-CE25-0001, taking place from October 2015 to March 2021.

Soutenances de thèses

Mardi 30 mars 2021, 9 heures 30, Online

**Ranadeep Biswas** (IRIF) *Automated Formal Testing of Storage Systems and Applications*

Modern distributed software is centered around using large-scale storage systems for storing and retrieving data. To ensure persistence and availability of data in the presence of failures, these systems maintain data in multiple copies that are stored on different nodes in the network. Then, for performance reasons, these copies are allowed to (temporarily) diverge, an instance of the so-called weak-consistency, which makes the semantics of concurrent accesses to data quite complex.

Over the recent years, many solutions for implementing weakly-consistent storage systems have been proposed. These implementations are most often very complex and error-prone. The specific levels of weak consistency they ensure are most often described only informally, which makes it difficult to reason about them. Moreover, in many cases, there are significant discrepancies between the guarantees claimed in their documentation and the guarantees that they really provide.

The objective of this dissertation is to propose algorithmic techniques for automated testing of weakly-consistent distributed systems against formal specifications. We focus on an important class of distributed data types, called Conflict-Free Replicated Data Types (CRDTs for short), that include many variations like registers, flags, sets, arrays, etc., and on Transactional Systems (Databases), which enable computations on shared data that are isolated from other concurrent computations and resilient to failures. We introduce formal specifications for such systems and investigate the asymptotic complexity of checking whether a given execution conforms to such specifications. We also study the problem of testing applications that run on top of weakly-consistent transactional systems, introducing a mock in-memory storage system that simulates the behaviors of such systems according to their formal specifications.

Soutenances de thèses

Lundi 15 mars 2021, 14 heures 30, Online

**Sidi Mohamed Beillahi** (IRIF) *Automated Verification of Programs Running on top of Distributed Systems*

The effect of a set of database transactions executing in parallel is specified using a formalism called consistency model. For instance, serializability states that a set of transactions behave as if they were executed serially one after another even if they actually overlap in time. Although simple to understand, serializability carries a significant penalty on performance and modern databases implement weaker consistency models. In general, these weak models are more complex to reason about. In this dissertation, we investigate the problem of checking a property of applications called robustness. Given two comparable consistency models, an application is called robust if it has the same behaviors when ran on top of databases implementing these two models. This dissertation investigates the theoretical complexity of checking robustness in the context of several consistency models: causal consistency, prefix consistency, snapshot isolation, and serializability. It provides non-trivial reductions to a well-studied problem in formal verification, assertion checking, that enables the reuse of existing verification technology. Besides theoretical results, it proposes pragmatic approaches based on under/over-approximations that are evaluated on practical applications.

Applications ran on top of blockchain are deployed in the form of smart contracts that manipulate the blockchain state. Smart contracts are mainly used to govern trading in cryptoassets that are worth billions of US dollars, and bugs can lead to huge financial losses. Exacerbating the impact of these bugs is the fact that smart contracts cannot be modified once they are deployed on the blockchain. Applying techniques from formal verification to audit smart contracts can help in avoiding expensive bugs. However, since most smart contracts are not annotated with formal specifications, formal verification of functional properties is impeded. To overcome this problem, this dissertation investigates notions of refinement between smart contracts, which enable the re-use of verified contracts as specifications for other contracts, thus scaling up the overall verification effort.

Soutenances de thèses

Jeudi 28 janvier 2021, 15 heures, Online

**Léonard Guetta** (IRIF) *Homology of strict omega-categories*

Soutenances de thèses

Vendredi 8 janvier 2021, 9 heures 30, Online

**Simon Forest** (IRIF) *Computational Description of Higher Categories*

#### Année 2020

Soutenances de thèses

Vendredi 4 décembre 2020, 14 heures, Online

**Isaac Konan** (IRIF) *Rogers-Ramanujan type identities: bijective proofs and Lie-theoretic approach*

Soutenances de thèses

Jeudi 26 novembre 2020, 13 heures, Online

**Alexandre Nolin** (IRIF) *Communication complexity: large output functions, partition bounds, and quantum nonlocality*

Soutenances de thèses

Lundi 23 novembre 2020, 10 heures, Remote

**Alessandro Luongo** (IRIF) *Quantum algorithms for machine learning*

Soutenances de thèses

Mercredi 4 novembre 2020, 15 heures, Online

**Brieuc Guinard** (IRIF) *Intermittent Lévy Walks and their applications in biological searches*

Soutenances de thèses

Jeudi 15 octobre 2020, 16 heures, Online

**Cédric Ho Thanh** (IRIF) *Opetopes: Syntactic and Algebraic Aspects*

This thesis develops the theory of opetopes along three main axes. First, we give it clean and robust foundations by carefully detailing the approach of Kock et. al., based on polynomial monads and trees. Then, with the aim of computerized manipulation in mind, we introduce two syntactical approaches to opetopes and opetopic sets. In each, opetopes are represented as syntactical constructs whose well-formation conditions are enforced by corresponding sequent calculi. Lastly, we focus on the algebraic structures that can naturally be described by opetopes. So-called opetopic algebras include categories, planar operads, and Loday's combinads over planar trees. We show how classical results of Rezk, Joyal and Tierney (for ∞-categories), and Cisinski and Moerdijk (for ∞-operads) can be reformulated and generalized in the opetopic setting.

Manuscript

Soutenances de thèses

Vendredi 26 juin 2020, 14 heures, Online

**Baptiste Louf** (IRIF) *Cartes de grand genre : de la hiérarchie KP aux limites probabilistes*

Manuscrit

Soutenances de thèses

Vendredi 12 juin 2020, 14 heures, Online

**Gianluca Curzi** (IRIF) *Non-laziness in implicit computational complexity and probabilistic λ-calculus*

#### Année 2019

Soutenances de thèses

Mardi 17 décembre 2019, 10 heures, Salle 0010, Bâtiment Sophie Germain

**Mengchuan Zou** (IRIF) *Aspects of Efficiency in Selected Problems of Computation on Large Graphs*

In the first work, we consider a setting of classical centralized computing, and we consider the question of generalizing modular decompositions and designing time-efficient algorithm for this problem. Modular decomposition, and more broadly module detection, are ways to reveal and analyze modular properties in structured data. As the classical modular decomposition is well studied and have an optimal linear-time algorithm, we firstly study the generalizations of these concepts to hypergraphs and present here positive results obtained for three definitions of modular decomposition in hypergraphs from the literature. We also consider the generalization of allowing errors in classical graph modules and present negative results for two this kind of definitions.

The second work focuses on graph data query scenarios. Here the model differs from classical computing scenarios in that we are not designing algorithms to solve an original problem, but we assume that there is an oracle which provides partial information about the solution to the original problem, where oracle queries have time or resource consumption, which we model as costs, and we need to have an algorithm deciding how to efficiently query the oracle to get the exact solution to the original problem, thus here the efficiency is addressing to the query costs. We study the generalized binary search problem for which we compute an efficient query strategy to find a hidden target in graphs. We present the results of our work on approximating the optimal strategy of generalized binary search on weighted trees.

Our third work draws attention to the question of memory efficiency. The setup in which we perform our computations is distributed and memory-restricted. Specif- ically, every node stores its local data, exchanging data by message passing, and is able to proceed local computations. This is similar to the LOCAL/CONGEST model in distributed computing, but our model additionally requires that every node can only store a constant number of variables w.r.t. its degree. This model can also describe natural algorithms. We implement an existing procedure of multiplicative reweighting for approximating the maximum s–t flow problem on this model, this type of methodology may potentially provide new opportunities for the field of local or natural algorithms.

From a methodological point of view, the three types of efficiency concerns cor respond to the following types of scenarios: the first one is the most classical one – given the problem, we try to design by hand the more efficient algorithm; the second one, the efficiency is regarded as an objective function – where we model query costs as an objective function, and using approximation algorithm techniques to get a good design of efficient strategy; the third one, the efficiency is in fact posed as a constraint of memory and we design algorithm under this constraint.

Soutenances de thèses

Lundi 16 décembre 2019, 14 heures 30, Salle 2017, Bâtiment Sophie Germain

**Adrien Husson** (IRIF) *Logical foundations of a modelling assistant for molecular biology*

Manuscript

Soutenances de thèses

Jeudi 12 décembre 2019, 14 heures, Salle 2014, Bâtiment Sophie Germain

**Théo Zimmermann** (IRIF) *Challenges in the collaborative evolution of a proof language and its ecosystem*

Recent years have seen important changes in the development processes of Coq, of which I have been a witness and an actor (adoption of GitHub as a development platform, first for its pull request mechanism, then for its bug tracker, adoption of continuous integration, switch to shorter release cycles, increased involvement of external contributors in the open source development and maintenance process). The contributions of this thesis include a historical description of these changes, the refinement of existing processes, and the design of new ones, the design and implementation of new tools to help the application of these processes, and the validation of these changes through rigorous empirical evaluation.

Involving external contributors is also very useful at the level of the package ecosystem. This thesis additionally contains an analysis of package distribution methods, and a focus on the problem of the long-term maintenance of single-maintainer packages.

Manuscript

Soutenances de thèses

Lundi 9 décembre 2019, 14 heures, Salle 3052, Bâtiment Sophie Germain

**Simon Collet** (IRIF) *Algorithmic Game Theory Applied to Networks and Populations*

Besides the introduction and the conclusion, the thesis is divided into three parts. In the first part, we adopt the point of view of classical game theory. We propose a game that corresponds to a wide class of problems encountered in the theory of distributed computing. The main contributions of this part are, on the one hand, to show how to transform a purely algorithmic problem into a game, and, on the other hand, to prove the existence of satisfactory equilibria for the resulting class of games. This second point is essential, as it guarantees that game theory is adapted to the study of distributed games, despite their complexity.

The second part is dedicated to the study of a game omnipresent within biological systems, that we call dispersion game. This game models the situation in which a group of animals must share a certain amount of resources scattered among different geographical sites. The difficulty of the game comes from the fact that some sites contain more resources than others, but may also attract more players. We propose a rule for the distribution of resources which makes it possible to maximize the resources exploited by the whole group. This part of the thesis is also an opportunity to revisit the close links between the concept of ideal free distribution, very present in the theory of foraging, and the concept of evolutionarily stable strategy, a key concept of evolutionary game theory.

The third part focuses on the study of the behavior of a specific species of small bats living in Mexico, in the Sonoran Desert, and feeding at night from the nectar of the giant Saguaro cacti, a protected species. After the presentation of the experimental results obtained in the field, we propose a computer simulation of their behavior. The results of these simulations make it possible to formulate interesting hypotheses about the cerebral activities of these small mammals. We then study a theoretical model of game inspired by this real situation. The study of this abstract model allows us to distinguish the fundamental characteristics of the game, and to reinforce our approach of theorizing foraging behavior. This study also opens the way to applying this type of model to other situations, involving animal or human behavior.

Soutenances de thèses

Vendredi 6 décembre 2019, 15 heures 30, Salle 1009, Bâtiment Sophie Germain

**Jules Chouquet** (IRIF) *Une Géométrie du calcul : Réseaux de preuve, Appel-Par-Pousse-Valeur et topologie du Consensus*

On étudie d’abord le développement de Taylor des réseaux de preuve de la Logique Linéaire. On introduit des méthodes de démonstration qui utilisent la géométrie de l’élimination des coupures des réseaux multiplicatifs, et qui permettent de manipuler des sommes infinies de réseaux de façon sûre et correcte, pour en extraire des propriétés sur les réductions qui sont à l’œuvre.

Ensuite, nous introduisons un langage permettant de définir le développement de Taylor syntaxique pour l’Appel-Par-Pousse-Valeur (Call-By-Push-Value), en capturant certaines propriétés de la sémantique dénotationelle liées aux morphismes de coalgèbres.

Puis nous nous intéressons aux systèmes distribués (à mémoire
partagée, tolérants aux pannes), et au problème du Consensus. On
utilise un modèle topologique qui permet d’interpréter la
communication dans les complexes simpliciaux, et on l’adapte de façon
à transformer les résultats d’impossibilité bien connus en résultats
de borne inférieure de probabilité pour des algorithmes probabilistes.

*English version:*

This Phd thesis presents a quantitative study of various computation
models of fundamental computer science and proof theory, in two
principad directions: the first consists in the examination of
mecanismis of multilinear approximations in systems related to
λ-calculus and Linear Logic. The second consists in a study of
topological models for asynchronous distributed systems, and
probabilistic algorithms.

We first study Taylor expansion in Linear Logic proof nets. We introduce proof methods using the geometry of cut elimination in multiplicative nets, and which allow to work with infinite sums of nets in a safe and correct way, in order to extract properties about reduction.

Then, we introduce a language allowing us to define Taylor expansion for Call-By-Push-Value, while capturing some properties of the denotational semantics, related to coalgebras morphisms.

We focus then on fault tolerant-distributed systems with shared
memory, and to Consensus problem. We use a topological model which
allows to interpret communication with simplicial complexes, and we
adapt in so as to transform the well-known impossibility results in
lower bounds for probabilistic algorithms.

Manuscript: https://www.irif.fr/~chouquet/these.html

Soutenances de thèses

Mardi 3 décembre 2019, 14 heures 30, Salle 3052, Bâtiment Sophie Germain

**Clément Jacq** (IRIF) *Categorical Combinatorics for Non-Deterministic Innocent Strategies*

Our starting point in the thesis is provided by the combinatorial approach to innocent strategies developed by Harmer, Hyland and Melliès in a work published ten years ago. In this work, they elaborate a combinatorial description of the pointer structures of arena games, and establish that innocence can be recovered by taking advantage of a number of remarkable categorical properties, most notably the existence of a distributive law between the monad generating the Player views and the comonad generating the Opponent views.

In this thesis, we study in great detail the reconstruction of the innocent game model identified by Harmer, Hyland and Melliès, and extend this model in two directions. In the first direction, we explain how to see the Harmer-Hyland-Melliès game model as a specific instance of a dialogue category, a notion originally introduced by Melliès, using the underlying symmetry between Opponent and Player in categories of games and strategies.

In the second direction, we construct a 2-dimensional game semantics of non-deterministic PCF by equipping every game with a presheaf of non-deterministic strategies, instead of just a set of strategies. In order to perform this shift of dimension from sets to presheaves, we adapt very carefully the categorical constructions involved in the Harmer-Hyland-Melliès model, and construct in particular a pseudo-distributive law between the pseudo-monad generating the Player views and the pseudo-comonad generating the Opponent views in our non-determinic game model. We obtain in this way a bicategory of games, non-deterministic innocent strategies and simulations — which we then compare with alternative formulations of non-deterministic and innocent game semantics appearing in the literature.

Soutenances de thèses

Lundi 30 septembre 2019, 14 heures, Bâtiment Sophie Germain

**Xin Ye** *Model checking self modifying code*

Soutenances de thèses

Mercredi 26 juin 2019, 14 heures, Bâtiment Sophie Germain

**Paulina Cecchi Bernales** (IRIF) *Invariant measures in symbolic dynamics: a topological, combinatorial and geometrical approach*

Soutenances de thèses

Vendredi 21 juin 2019, 15 heures, Amphithéâtre Turing, Bâtiment Sophie Germain

**Enka Blanchard** (IRIF) *Usability: low tech, high security*

Soutenances de thèses

Jeudi 20 juin 2019, 14 heures 30, Salle 0011

**Raphaëlle Crubillé** (IRIF) *Behavioural distances for higher-order probabilistic programs*

Soutenances de thèses

Jeudi 14 mars 2019, 14 heures, Bâtiment Sophie Germain

**Tommaso Petrucciani** (IRIF) *Polymorphic set-theoretic types for functional languages*

#### Année 2018

Soutenances de thèses

Vendredi 7 décembre 2018, 14 heures, Salle François Jacob, bâtiment Buffon

**Pierre Cagne** (IRIF) *Towards a homotopical algebra of dependent types*

Soutenances de thèses

Vendredi 30 novembre 2018, 14 heures 30, Salle 580F, Bâtiment Halle aux Farines

**Lucas Boczkowski** (IRIF) *Search and Broadcast in Stochastic Environments, a Biological Perspective*

The first model studied in this thesis takes its inspiration in collaborative transport of food in the P. Longicornis ant species. We find that some key aspects of the process are well described by a graph search problem with noisy advice. The advice corresponds to characteristic short scent marks laid in front of the load in order to facilitate its navigation. In this thesis, we provide detailed analysis of the model on trees, which are relevant graph structures from a computer science standpoint. In particular our model may be viewed as a noisy extension of binary search to trees. Tight results in expectation and high probability are derived with matching upper and lower bounds. Interestingly, there is a sharp phase transition phenomenon for the expected runtime, but not when the algorithms are only required to succeed with high probability.

The second model we work with was initially designed to capture information broadcast amongst desert ants. The model uses a stochastic meeting pattern and noise in the interactions, in a way that matches experimental data. Within this theoretical model, we present in this document a strong lower bound on the number of interactions required before information can be spread reliably. Experimentally, we see that the time required for the recruitment process of even few ants increases sharply with the group size, in accordance with our result. A theoretical consequence of the lower bound is a separation between the uniform noisy PUSH and PULL models of interaction. We also study a close variant of broadcast, without noise this time but under more strict convergence requirements and show that in this case, the problem can be solved efficiently, even with very limited exchange of information on each interaction.

Soutenances de thèses

Vendredi 23 novembre 2018, 14 heures, Laboratoire MAP5, 45 rue des Saint-pères, 7eme étage, salle du conseil

**Léo Planche** (IRIF) *Décomposition de graphes en plus courts chemins et en cycles de faible excentricité*

Soutenances de thèses

Vendredi 19 octobre 2018, 9 heures 30, Salle 580F (salle des thèses), Bâtiment Halle aux Farines

**Marie Kerjean** (IRIF) *Reflexive spaces of smooth functions: a logical account for linear partial differential equations*

This manuscript strengthens the link between proof-theory and functional analysis, and highlights the role of linear involutive negation in DiLL. The first part of this thesis consists in an overview of prerequisites on the notions of linearity, polarisation and differentiation in proof-theory, and gives the necessary background in the theory of locally convex topological vector spaces. The second part uses two standard topologies on the dual of a topological vector space and gives two models of DiLL: the weak topology allows only for a discrete interpretation of proofs through formal power series, while the Mackey topology on the dual allows for a smooth and polarised model of DiLL. Finally, the third part interprets proofs of DiLL by distributions. We detail a polarized model of DiLL in which negatives are Fr\'echet Nuclear spaces, and proofs are distributions with compact support. We show that solving linear partial differential equations with constant coefficients can be typed by a syntax similar to the one of DiLL, which we detail.

Soutenances de thèses

Jeudi 27 septembre 2018, 15 heures 30, Salle 470E, Bâtiment Halle aux Farines

**Pablo Rotondo** (IRIF) *Probabilistic studies in Number Theory and Word Combinatorics: instances of dynamical analysis*

Sturmian words are a fundamental family of words in Word Combinatorics. They are in a precise sense the simplest infinite words that are not eventually periodic. Sturmian words have been well studied over the years, notably by Morse and Hedlund (1940) who demonstrated that they present a notable number theoretical characterization as discrete codings of lines with irrational slope, relating them naturally to dynamical systems, in particular the Euclidean dynamical system. These words have never been studied from a probabilistic perspective. Here, we quantify the recurrence properties of a “random” Sturmian word, which are dictated by the so-called “recurrence function”; we perform a complete asymptotic probabilistic study of this function, quantifying its mean and describing its distribution under two different probabilistic models, which present different virtues: one is a naturaly choice from an algorithmic point of view (but is innovative from the point of view of dynamical analysis), while the other allows a natural quantification of the worst-case growth of the recurrence function. We discuss the relation between these two distinct models and their respective techniques, explaining also how the two seemingly different techniques employed could be linked through the use of the Mellin transform. In this dissertation we also discuss our ongoing work regarding two special families of Sturmian words: those associated with a quadratic irrational slope, and those with a rational slope (not properly Sturmian). Our work seems to show the possibility of a unified study.

The Continued Logarithm Algorithm, introduced by Gosper in Hakmem (1978) as a mutation of classical continued fractions, computes the greatest common divisor of two natural numbers by performing division-like steps involving only binary shifts and substractions. Its worst-case performance was studied recently by Shallit (2016), who showed a precise upper-bound for the number of steps and gave a family of inputs attaining this bound. In this dissertation we employ dynamical analysis to study the average running time of the algorithm, giving precise mathematical constants for the asymptotics, as well as other parameters of interest. The underlying dynamical system is akin to the Euclidean one, and was first studied by Chan (around 2005) from an ergodic, but the presence of powers of 2 in the quotients ingrains into the central parameters a dyadic flavour that cannot be grasped solely by studying this system. We thus introduce a dyadic component and deal with a two-component system. With this new mixed system at hand, we then provide a complete average-case analysis of the algorithm by Dynamical Analysis.

Soutenances de thèses

Mercredi 26 septembre 2018, 14 heures, Bâtiment Sophie Germain

**Vitalii Aksenov** (IRIF) *Synchronization costs in parallel programs and concurrent data structures*

Soutenances de thèses

Mardi 25 septembre 2018, 14 heures, Salle 3052, Bâtiment Sophie Germain

**Yann Hamdaoui** (IRIF) *Concurrency, References and Linear Logic*

Soutenances de thèses

Jeudi 20 septembre 2018, 10 heures, 1828 (Olympe de Gouges)

**Matthieu Boutier** *Routage sensible à la source*

Pot en 3052 à Sophie Germain.

Soutenances de thèses

Mercredi 19 septembre 2018, 14 heures, Salle 3052, Bâtiment Sophie Germain

**Laurent Feuilloley** (IRIF) *Certification locale en calcul distribué : sensibilité aux erreurs, uniformité, redondance et interactivité*

Du fait de la contrainte de localité, peu de prédicats peuvent être vérifiés de cette manière. La certification locale est un moyen de contourner cette difficulté, et permet de décider tous les prédicats. C'est un mécanisme qui consiste à étiqueter les nœuds du réseau avec ce que l'on appelle des certificats, qui peuvent être vérifiés localement par un algorithme distribué. Un schéma de certification locale est correct si seuls les réseaux dans une configuration correcte peuvent être certifiés. L'idée de la certification locale est non seulement séduisante d'un point de vue théorique, comme une forme de non-déterminisme distribué, mais c'est surtout un concept très utile pour l'étude des algorithmes tolérants aux pannes, où une étape-clé consiste à vérifier l'état du réseau en se basant sur des informations stockées par les nœuds.

Cette thèse porte sur quatre aspects de la certification locale : la sensibilité aux erreurs, l'uniformité, la redondance et l'interactivité. L'étude de ces quatre sujets est motivée par une question essentielle : comment réduire les ressources nécessaires à la certification et/ou permettre une meilleure tolérance aux pannes? Pour aborder cette question, il est nécessaire de comprendre le mécanisme de certification en profondeur. Dans cette optique, dans cette thèse, nous apportons des réponses aux questions suivantes. À quel point les certificats doivent-ils être redondants, pour assurer une certification correcte? Les schémas de certification classiques sont-ils robustes à un changement de la condition de correction? Le fait d'introduire de l'interactivité dans le processus change-t-il la complexité de la certification?

Mots-clefs: Calcul distribué sur réseau, décision distribuée, certification locale, schéma d'étiquetage de preuve, tolérance aux pannes.

Soutenances de thèses

Mardi 18 septembre 2018, 14 heures, 580F (Halle aux Farines)

**Guillaume Claret** (IRIF) *Program in Coq*

First, we work on two preliminary projects helping us to understand the challenges of programming in Coq. The first project, Cybele, is a Coq plugin to write efficient proofs by reflection with effects. We compile and execute the impure effects in OCaml to generate a prophecy, a kind of certificate, and then interpret the effects in Coq using the prophecy. The second project, the compiler CoqOfOCaml, imports OCaml programs with effects into Coq, using an effect inference system.

Next, we describe different generic and composable representations of impure effects in Coq. The breakable computations combine the standard exceptions and mutable references effects, with a pause mechanism to make explicit the evaluation steps in order to represent the concurrent evaluation of two terms. By implementing the Pluto web server in Coq, we realize that the most important effects to program are the asynchronous inputs-outputs. Indeed, these effects are ubiquitous and cannot be encoded in a purely functional manner. Thus, we design the asynchronous computations as a first way to represent and compile programs with events and handlers in Coq.

Then, we study techniques to prove properties about programs with effects. We start with the verification of the blog system ChickBlog written in the language of the interactive computations. This blog runs one worker with synchronous inputs-outputs per client. We verify our blog using the method of specification by use cases. We adapt this technique to type theory by expressing a use case as a well-typed co-program over the program we verify. Thanks to this formalism, we can present a use case as a symbolic test program and symbolically debug it, step by step, using the interactive proof mode of Coq. To our knowledge, this is the first such adaptation of the use case specifications in type theory. We believe that the formal specification by use cases is one of the keys to verify effectful programs, as the method of use cases proved to be convenient to express (informal) specifications in the software industry. We extend our formalism to concurrent and potentially non-terminating programs with the language of concurrent computations. Apart from the use case method, we design a model-checker to verify the deadlock freeness of concurrent computations, by compiling the parallel composition to the non-deterministic choice operator.

Soutenances de thèses

Lundi 10 septembre 2018, 14 heures, Amphi Turing, Bâtiment Sophie Germain

**Luca Reggio** (IRIF) *Quantifiers and duality*

We contribute to the semantic understanding of quantifiers, from the viewpoint of duality theory, in three different areas of mathematics and theoretical computer science. First, in formal language theory through the syntactic approach provided by logic on words. Second, in intuitionistic propositional logic and in the study of uniform interpolation. Third, in categorical topology and categorical semantics for predicate logic.

Soutenances de thèses

Lundi 10 septembre 2018, 14 heures, Bâtiment Sophie Germain

**Bin Fang** (IRIF) *Techniques for formal modelling and verification on dynamic memory allocators*

Soutenances de thèses

Jeudi 5 juillet 2018, 14 heures 30, 580F (halle aux farines)

**Guillaume Lagarde** (IRIF) *Contributions to Arithmetic Complexity and Compression*

Soutenances de thèses

Jeudi 5 juillet 2018, 14 heures, Room B107 of LIPN, Université Paris 13

**Huu Vu Nguyen** (IRIF) *On CARET Model-Checking of Pushdown Systems: Application to Malware Detection*

Soutenances de thèses

Jeudi 5 juillet 2018, 10 heures, Salle B107 du LIPN, Université Paris 13

**Adrien Pommellet** (IRIF) *On Model-checking Pushdown System Models*

Soutenances de thèses

Mardi 3 juillet 2018, 14 heures, Room B107 of LIPN, Université Paris 13

**Khanh Huu The Dam** (IRIF) *Automatic Learning and Extraction of Malicious Behaviors*

Soutenances de thèses

Mardi 3 juillet 2018, 14 heures, Salle 580F (Halle aux Farines)

**Thibaut Girka** (IRIF) *Differential program semantics*

Soutenances de thèses

Vendredi 15 juin 2018, 14 heures, Bâtiment Sophie Germain

**Clément Dervieux** (IRIF) *Enumeration of oriented planar maps*

Soutenances de thèses

Vendredi 25 mai 2018, 15 heures, Salle 0010, Bâtiment Sophie Germain

**Florent Urrutia** (IRIF) *Information Theory for Multi-Party Peer-to-Peer Communication Protocols*

Soutenances de thèses

Vendredi 27 avril 2018, 14 heures, Salle 1021, Bâtiment Sophie Germain

**Alex B. Grilo** (IRIF) *Quantum proofs, the Local Hamiltonian problem and applications*

#### Année 2017

Soutenances de thèses

Mardi 12 décembre 2017, 14 heures 30, Salle 1009, Sophie Germain

**Fabian Reiter** (IRIF) *Distributed Automata and Logic*

Manuscript: https://www.irif.fr/~reiterf

Soutenances de thèses

Jeudi 7 décembre 2017, 14 heures 30, Amphi 10E, Halle aux Farines

**Pierre Vial** (IRIF) *Non-idempotent typing operators, beyond the lambda-calculus*

- Nous proposons d'abord une caractérisation de la normalisation de tête et de la normalisation forte du lambda-mu calcul (déduction naturelle

classique) en introduisant des types unions non-idempotents. Comme dans le cas intuitionniste, la non-idempotence nous permet d'extraire du typage des informations quantitatives ainsi que des preuves de terminaison beaucoup plus élémentaires que dans le cas idempotent. Ces résultats nous conduisent à définir une variante à petits pas du lambda-mu-calcul, dans lequel la normalisation forte est aussi caractérisée avec des méthodes quantitatives.

- Dans un deuxième temps, nous étendons la caractérisation de la normalisation faible dans le lambda-calcul pur à un lambda-calcul infinitaire étroitement lié aux arbres de Böhm et dû à Klop et al. Ceci donne une réponse positive à une question connue comme le problème de Klop. À cette fin, il est nécessaire d'introduire conjointement un système (système S) de types infinis utilisant une intersection que nous qualifions de séquentielle, et un critère de validité servant à se débarrasser des preuves dégénérées auxquelles les grammaires coinductives de types donnent naissance. Ceci nous permet aussi de donner une solution au problème n°20 de TLCA (caractérisation par les types des permutations héréditaires). Il est à noter que ces deux problèmes n'ont pas de solution dans le cas fini (Tatsuta, 2007).
- Enfin, nous étudions le pouvoir expressif des grammaires coinductives de types, en dehors de tout critère de validité. Nous devons encore recourir au système S et ous montrons que tout terme est typable de façon non triviale avec des types infinis et que l'on peut extraire de ces typages des informations sémantiques comme l'ordre (arité) de n'importe quel lambda-terme. Ceci nous amène à introduire une méthode permettant de typer des termes totalement non-productifs, dits termes muets, inspirée de la logique du premier ordre. Ce résultat prouve que, dans l'extension coinductive du modèle relationnel, tout terme a une interprétation non vide. En utilisant une méthode similaire, nous montrons aussi que le système S collapse surjectivement sur l'ensemble des points de ce modèle.

Soutenances de thèses

Vendredi 1 décembre 2017, 14 heures 30, Salle des Thèses, Halle aux Farines

**Maxime Lucas** (IRIF) *Cubical categories for homotopy and rewriting*

Soutenances de thèses

Vendredi 17 novembre 2017, 15 heures 15, Salle 153, Olympe de Gouges

**Etienne Miquey** (IRIF) *Classical realizability and side-effects*

Soutenances de thèses

Mardi 14 novembre 2017, 11 heures, Salle des Thèses, Halle aux Farines

**Gabriel Radanne** (IRIF) *Tierless Web programming in ML*

Soutenances de thèses

Vendredi 1 septembre 2017, 10 heures, Salle 2014, Bâtiment Sophie Germain

**Jovana Obradović** (IRIF) *Cyclic operads: syntactic, algebraic and categorified aspects*

Soutenances de thèses

Jeudi 13 juillet 2017, 14 heures 30, Amphithéâtre Turing, Bâtiment Sophie Germain

**Thibault Godin** (IRIF) *Mealy machines, automaton (semi)groups,decision problems and random generation*

Soutenances de thèses

Vendredi 7 juillet 2017, 14 heures, Salle 0010, Bâtiment Sophie Germain

**Bruno Karelovic** (IRIF) *Quantitative analysis of stochastic systems : priority games and populations of Markov chains*

Soutenances de thèses

Mardi 27 juin 2017, 10 heures, Salle 255, Olympe de Gouges

**Amina Doumane** (IRIF) *On the infinitary proof theory of logics with fixed points*

Soutenances de thèses

Mardi 7 février 2017, 16 heures, Amphithéâtre Turing, Bâtiment Sophie Germain

**Mathieu Lauriere** (IRIF) *Complexites de communication et d'information dans les modèles classique et quantique*

#### Année 2016

Soutenances de thèses

Vendredi 9 décembre 2016, 14 heures, Salle des Thèses, Halle aux Farines

**Cyrille Chenavier** (IRIF) *Le treillis des opérateurs de réduction : applications aux bases de Gröbner non commutatives et en algèbre homologique*

Soutenances de thèses

Mardi 11 octobre 2016, 14 heures, Salle 1006, Sophie Germain

**Wenjie Fang** (IRIF) *Aspects énumératifs et bijectifs des cartes combinatoires : généralisation, unification et application*

Les cartes combinatoires sont un modèle combinatoire riche. Elles sont définies d’une manière intuitive et géométrique, mais elles sont aussi liées à des structures algébriques plus complexes. À la rencontre de différents domaines, les cartes peuvent être analysées par une grande variété de méthodes, et leur énumération peut aussi nous aider à compter d’autres objets combinatoires. Cette thèse présente un ensemble de résultats et de connexions très riches dans le domaine de l’énumération des cartes. Les résultats dans cette thèse se divise en deux grandes parties. La première partie contient mes travaux sur l'énumération des constellations, en utilisant les caractères du groupe symétrique ou bien en résolvant des équations fonctionnelles sur leur séries génératrices. La deuxième partie est sur le lien énumératif entre les cartes et d’autres objets combinatoires, par exemple les généralisations du treillis de Tamari et les graphes aléatoires qui peuvent être plongés dans une surface donnée.

Soutenances de thèses

Vendredi 8 avril 2016, 10 heures, Salle 2011, Sophie Germain

**Charles Grellois** (IRIF) *Sémantique de la logique linéaire et model-checking d'ordre supérieur*