Research

PhD thesis (from September 2024)

Enumeration problems and descriptive complexity
Paris-Cité University (France), Mathematics Institute of Jussieu-Paris Rive Gauche (IMJ-PRG),
Supervisor: Arnaud Durand, Co-supervisor: Yann Strozecki

The most studied computational problems are decision problems: for a given instance, is there a solution or not. On their side, enumeration problems are interested in enumerating all the solutions. Unlike decision or optimization problems, where complexity is generally measured in the size of the problem instance, complexity measures in enumeration must take into account the potentially exponential number of solutions to be enumerated. For this, several "tractable" complexity classes have been introduced: polynomial output time, polynomial incremental time, polynomial delay…
This thesis proposes to study the descriptive complexity of enumeration problems, by seeking logical characterizations for these classes. For polynomial output time, this would consist in exhibiting a logic L such that for any problem P (of graph for example): P is expressible in L if and only if P is enumerable in polynomial output time. Such results can be seen as algorithmic meta-theorems, in the sense that they automatically provide an algorithm (whether deciding on a problem, generating a solution or enumerating them all) from the expressions obtained in the logic.

Research internships

M2 research internship (14 weeks: from April 2024 to July 2024)

Team semantics and the flattening operator
University of Helsinki (Finland), Department of Mathematics and Statistics,
Supervisors: Juha Kontinen, Jouko Väänänen and Arnaud Durand

Team semantics was developed to describe the concepts of dependence and independence using formal logic. Over the formulas of first-order logic, this team semantics constitutes an extension of classical semantics, called Tarskian semantics. We can then study many types of dependencies: dependence, independence, inclusion, exclusion, etc. The starting point of this internship was the introduction of an operator F called the flattening operator. The natural question that follows adding such an operator to a given team-based logic is how much the expressive power of the given logic has been increased. Initially, the goal was to understand the expressiveness of the dependance logic expanded with F, the inclusion logic expanded with F, etc. A second phase was to obtain translations towards SAT problems, in order to understand the difficulty in terms of complexity brought by the addition of this operator F.

M2 research internship (20 weeks: from February 2023 to July 2023)

Logical characterization of enumeration complexity classes
Paris-Diderot University (France), Mathematics Institute of Jussieu-Paris Rive Gauche (IMJ-PRG),
Supervisor: Arnaud Durand

Enumeration problems are problems for which one wishes to enumerate all the solutions associated with an input instance. During this internship, we were interested in characterizing the complexity classes of enumeration problems (OutputP, IncP and DelayP) via certain logics. To achieve this, we had to develop fragments of third-order logic (mainly an existential third-order Horn logic) to first of all succeed in expressing central problems, such as max independent set or SAT, and then be able to capture enumeration complexity classes.

M1 research internship (12 weeks: from April 2022 to July 2022)

A characterization of the Hanf locality via an invariant elementary definability
University of Cambridge (England), Department of Computer Science and Technology,
Supervisor: Anuj Dawar

The Hanf locality intuitively says that structures that locally look the same cannot be distinguished by first order sentences. In a 2017 publication, Lindell, Towsner and Weinstein showed that a class of bounded degree structures is Hanf local, under certain conditions. The goal of this interneship was to extend this result to classes of unbounded degree structures, in particular by focusing on bounded tree-width structures.

L3 research internship (6 weeks: from May 2021 to July 2021)

One-way cellular automata and undecidability
University of Orléans (France), Fundamental Computer Science Laboratory of Orléans (LIFO), GAMoC team,
Supervisors: Martin Delacourt and Nicolas Ollinger

The periodicity problem for cellular automata is known to be undecidable in the general case. It has been shown that even if we restrict ourselves to the case of dimension 1, the problem remains undecidable. However, the problem is still open for the case of one-way cellular automata, in other words 1D cellular automata which can "see" only on one side. During this internship, we were interested in the preservation of the periodic property of one-way cellular automata under a certain transformation: the embedding.