# PhD Position F/M Descriptive complexity of topological invariants

**Contract type : **
Fixed-term contract

**Level of qualifications required : **
Graduate degree or equivalent

**Other valued qualifications : **
M2

**Fonction : **
PhD Position

## Context

This project will be carried out in the Inria team Mocqua, which focuses on emerging models of computation, in particular the interaction between discrete computations and continuous mathematics.

## Assignment

This PhD project is about the complexity of detecting topological properties of sets. The language of mathematics enables one to define continuous sets of points using a few symbols only. Typical examples are the solution set of an equation, or the attractor of a dynamical system. However, such finite descriptions do not give much information about the set itself and in particular its topology: its connectedness properties, its dimension, the existence of holes, etc.

The goal of this project is, given an access to a subset of the plane or a higher-dimensional Euclidean space, to understand how much of the topology of the set can be recovered, and what is the difficulty of the detection. This project lies at the interface between algorithmics, logic and topology. Techniques from continuous mathematics need to be used. In particular, the complexity is measured using descriptive set theory, which provides hierarchies and complexity classes of subsets of topological spaces, and is intimately related to logic [1].

## Main activities

The topic is vast and we propose to follow two particular directions.

The first axis is the investigation of the complexity of topological invariants. The literature on the topic shows that most of the invariants provided by topology have very high complexity (see [2], [3] for instance). Therefore, one needs to identify properties that can be detected with a low complexity budget. We propose several approaches to tackle this problem. Given a particular class of spaces, determine the minimal complexity of separating all the spaces of this class. In particular, given two distinct spaces, determine the exact complexity of distinguishing between them. For each particular space, determine the complexity of recognizing this space, i.e. of checking that an arbitrary space is isomorphic to that space. A first step in these directions has been initiated in [4], analyzing the case of finite topological graphs, and the more general case of finite simplicial complexes is still to be understood.

The second axis is about the complexity of theorems coming from topology. When a theorem asserts the existence of an object under certain asumptions, one needs to understand the difficulty of producing this object with an algorithm. The student will investigate the complexity of various theorems, such as characterizations of the arc, the circle or more complicated spaces, or characterizations of the continuous images of the arc. There are several possible frameworks to investigate the difficulty of theorems, namely descriptive set theory [1], reverse mathematics [5] and Weihrauch degrees [6].

#### References

[1] A. S. Kechris. Classical Descriptive Set Theory. Springer, January 1995.

[2] H. Becker. Descriptive set theoretic phenomena in analysis and topology. In Set Theory of the Continuum, New York, 1992. Springer US.

[3] G. Debs and J. Saint Raymond. The descriptive complexity of connectedness in Polish spaces. Fundamenta Mathematicae, 249(3):261–286, 2020.

[4] D. E. Amir and M. Hoyrup. Descriptive complexity of topological invariants. Preprint, 2023.

[5] D. D. Dzhafarov, C. Mummert. Reverse Mathematics. Springer, 2022.

[6] V. Brattka, G. Gherardi, A. Pauly. Weihrauch Complexity in Computable Analysis. In Handbook of Computability and Complexity in Analysis, Springer, 2021.

## Skills

- Master degree in theoretical computer science or mathematical logic
- Interest in topology and computability theory

## Benefits package

- Subsidized meals
- Partial reimbursement of public transport costs
- Leave: 7 weeks of annual leave + 10 extra days off due to RTT (statutory reduction in working hours) + possibility of exceptional leave (sick children, moving home, etc.)
- Possibility of teleworking (after 6 months of employment) and flexible organization of working hours
- Professional equipment available (videoconferencing, loan of computer equipment, etc.)
- Social, cultural and sports events and activities
- Access to vocational training
- Social security coverage

## Remuneration

2100€ gross/month the 1st year

## General Information

**Theme/Domain :**Proofs and Verification**Town/city :**Villers lès Nancy**Inria Center :**Centre Inria de l'Université de Lorraine**Starting date :**2024-10-01**Duration of contract :**3 years**Deadline to apply :**2024-05-12

**Warning** : you must enter your e-mail address in order to save your application to Inria. Applications must be submitted online on the Inria website. Processing of applications sent from other channels is not guaranteed.

## Instruction to apply

**Defence Security : **

This position is likely to be situated in a restricted area (ZRR), as defined in Decree No. 2011-1425 relating to the protection of national scientific and technical potential (PPST).Authorisation to enter an area is granted by the director of the unit, following a favourable Ministerial decision, as defined in the decree of 3 July 2012 relating to the PPST. An unfavourable Ministerial decision in respect of a position situated in a ZRR would result in the cancellation of the appointment.

** Recruitment Policy :**

As part of its diversity policy, all Inria positions are accessible to people with disabilities.

## Contacts

**Inria Team :**MOCQUA-
**PhD Supervisor :**

Hoyrup Mathieu / mathieu.hoyrup@inria.fr

## About Inria

Inria is the French national research institute dedicated to digital science and technology. It employs 2,600 people. Its 200 agile project teams, generally run jointly with academic partners, include more than 3,500 scientists and engineers working to meet the challenges of digital technology, often at the interface with other disciplines. The Institute also employs numerous talents in over forty different professions. 900 research support staff contribute to the preparation and development of scientific and entrepreneurial projects that have a worldwide impact.