PhD Position F/M Descriptive complexity of topological invariants
Type de contrat : Fixed-term contract
Niveau de diplôme exigé : Graduate degree or equivalent
Autre diplôme apprécié : M2
Fonction : PhD Position
Contexte et atouts du poste
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.
Mission confiée
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].
Principales activités
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.
Compétences
- Master degree in theoretical computer science or mathematical logic
- Interest in topology and computability theory
Avantages
- 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
Rémunération
2100€ gross/month the 1st year
Informations générales
- Thème/Domaine : Proofs and Verification
- Ville : Villers lès Nancy
- Centre Inria : Centre Inria de l'Université de Lorraine
- Date de prise de fonction souhaitée : 2024-10-01
- Durée de contrat : 3 years
- Date limite pour postuler : 2024-04-29
Attention: Les candidatures doivent être déposées en ligne sur le site Inria. Le traitement des candidatures adressées par d'autres canaux n'est pas garanti.
Consignes pour postuler
Sécurité défense :
Ce poste est susceptible d’être affecté dans une zone à régime restrictif (ZRR), telle que définie dans le décret n°2011-1425 relatif à la protection du potentiel scientifique et technique de la nation (PPST). L’autorisation d’accès à une zone est délivrée par le chef d’établissement, après avis ministériel favorable, tel que défini dans l’arrêté du 03 juillet 2012, relatif à la PPST. Un avis ministériel défavorable pour un poste affecté dans une ZRR aurait pour conséquence l’annulation du recrutement.
Politique de recrutement :
Dans le cadre de sa politique diversité, tous les postes Inria sont accessibles aux personnes en situation de handicap.
Contacts
- Équipe Inria : MOCQUA
-
Directeur de thèse :
Hoyrup Mathieu / mathieu.hoyrup@inria.fr
A propos d'Inria
Inria est l’institut national de recherche dédié aux sciences et technologies du numérique. Il emploie 2600 personnes. Ses 215 équipes-projets agiles, en général communes avec des partenaires académiques, impliquent plus de 3900 scientifiques pour relever les défis du numérique, souvent à l’interface d’autres disciplines. L’institut fait appel à de nombreux talents dans plus d’une quarantaine de métiers différents. 900 personnels d’appui à la recherche et à l’innovation contribuent à faire émerger et grandir des projets scientifiques ou entrepreneuriaux qui impactent le monde. Inria travaille avec de nombreuses entreprises et a accompagné la création de plus de 200 start-up. L'institut s'efforce ainsi de répondre aux enjeux de la transformation numérique de la science, de la société et de l'économie.