Missions

La théorie algorithmique de l'information et la théorie descriptive effective des ensembles offrent un nouvel éclairage sur de nombreux concepts basés sur la théorie de la mesure, tels que les probabilités ou la dimension de Hausdorff. Des avancées récentes du domaine ont permis de relier les propriétés géométriques d'un ensemble à la complexité logique de ses points. Ces nouvelles techniques ont été appliquées avec succès pour étendre des résultats existants à des classes plus larges d'ensembles (au-delà des ensembles analytiques), mais aussi pour expliciter les raisons pour lesquelles, dans d'autres cas, une telle extension est impossible. Dans cette veine, citons notamment le théorème de projection de Marstrand et la capacité des ensembles de nombres réels. Le candidat recruté sera essentiellement amené à travailler sur les grandes lignes suivantes:

1) Principe de transfert du point à l'ensemble (en anglais: `point-to-set' principles): Il existe une correspondance étroite entre la dimension de Hausdorff classique d'un ensemble dans l'espace euclidien et la dimension de Hausdorff effective de ses points. Les questions relatives à la dimension de Hausdorff d'un ensemble peuvent donc être traduites en questions relatives au caractère aléatoire relatif et à la dimension effective de points individuels. Dans quelle mesure ce principe s'étend-il aux fonctions de jauge générales et aux espaces métriques autres qu'euclidiens ?

2) Vers une notion locale de la dimension de Fourier: Le transfert du point à l'ensemble pour la dimension de Hausdorff peut être vu comme un exemple de correspondance locale-globale pour la dimension de Hausdorff des mesures. Pour la dimension de Fourier d'une mesure (définie sur la base du comportement asymptotique des coefficients de Fourier-Stieltjes d'une mesure - une propriété globale), une telle correspondance n'est actuellement pas connue.

3) De quelles classes de calcul a-t'on besoin ? Dans les travaux mentionnés ci-dessus, on utilise la complexité de Kolmogorov classique, qui est un outil puissant mais peut poser problème conceptuellement car elle n'est pas une fonction calculable. Des variantes faibles existent, basées par exemple sur des classes de complexité comme PTIME, ou sur des modèles de calculs moins expressifs comme les automates finis. On se propose d'étudier si de telles variantes admettent des principes de transfert suffisamment puissants pour les points décrits ci-dessus.

Activités

Les activités afférentes à ce projet sont les activités de recherche habituelles dans les domaines théoriques: travail de recherche collaboratif, présentations, encadrement éventuel de stagiaires, participation à la vie de l'équipe (séminaires, etc).

Compétences

Doctorat en Informatique ou Mathématiques avec spécialisation en théorie de la calculabilité ou domaine connexe.

Contexte de travail

Le candidat ou la candidate retenu(e) sera intégré(e) à l'équipe Logique et Fondements du Calcul.

Le poste se situe dans un secteur relevant de la protection du potentiel scientifique et technique (PPST), et nécessite donc, conformément à la réglementation, que votre arrivée soit autorisée par l'autorité compétente du MESR.

Contraintes et risques

Pas de contraintes ni risques particuliers liés à cette offre.