Research

Here are some of my academic activities.

Internship at LIX, France — April to july 2025

Subject : computational complexity for functions ; circuits and different Kolmogorov complexity

Find here my report. Slides for a 15 minutes presentation during my defence are also available.

Research project at LIX, France — September 2024 to March 2025

Subject : Introduction to Computable Analysis

In addition to my master’s courses, I had the opportunity, thanks to Olivier Bournez, to undertake a part-time research project divided into two phases:

1. Type 2 recursion theory (in English)
2. Complete problems in computable analysis (in French, with an English abstract)

The main result of this work was to rephrase and present some results from Vasco Brattka: the problem lim, which returns the limit of a converging sequence, is Σ₂-complete. (See the report 2.)

Internship at LISN, France — May to August 2024

Subject : Factorization in semi-groups diagrams

This internship in the team Graphs, ALgorithms and Combinatorics (GALaC) supervised by Florent Hivert and Adeline Pierrot was divided in two major parts :

• An experimental phase, where I became familiar with objects we where manipulating, and where I have written a library to compute semigroups we were studying, and looked for semi-groups with nice properties
• A more theoretical part, where I constructed and proved, based on Florent works, a factorization theorem, that allows to build minimal representations of Okada’s monoid elements, as product of generators.

There was two things that characterize well our works :

• the composition law used : diagram composition, which came natural when done “by hands”, but also which formalizes well. Based on the partition monoid, where elements generalize the notion of function.
• In addition to classical partition diagrams, we where labelling arcs –or in other words, equivalence classes– and adding to the diagrams composition law a binary function that given the labels of two classes, returns the label of the union class.

Experimenting and writing a library

Indeed, Florent established a bijection between Young-Fibonacci Lattices and labelled-arc diagrams that followed few properties (called Okada diagrams), which shows the importance of these labelled-arc diagrams. This has motivated the writing of a library allowing to calculated dimensions of submonoids of partition monoid. Here are my results :

It gives from a submonoid of partition monoid and a size of diagrams n, the size of the generated set.

By allowing different kind of generators and labelling their edge like Florent did for its correspondence (take as label for a classe the minimum of elements in this class), we calculate these values.

Factorize Okada’s labelled arc-diagrams

The second important part of my works was to find out how to decompose a given element of Okada’s monoid, i.e given a element x, find all elements x’ such that there exists a generator g that gives :

1. x = x’ . g
2. length(x) = length(x’) + length(g)

Florent already found factorization depending on specific element x’ (with has the lowest generators associated), and me I had to generalize it to all possible elements.

Then, I had to write a consistent proof showing that this factorization works effectively, by formalizing our intuition and by introducing useful notions.

Knowing that, we can quite easily generate all minimal factorizations without using relations over the semi-group (which would be quite bad computably-speaking).

My report

Experiment results are provided in part 3 of my report, while the factorization theorem (2.17) and proof are detailed in section 2.1. The report summarizes my work and understanding of the subject. It’s in French, but with an English abstract.

The code written for the library is available here.