Lundi 22 juin à 14h
Résumé :
Cette thèse est consacrée au développement et à l’étude de modèles probabilistes avec structure spatiale. Les problèmes envisagés font aussi bien partie de la physique statistique des systèmes désordonnés que du domaine de l’inférence statistique en informatique. L’intérêt de la structure spatiale est de pouvoir introduire des modèles concrets directement interprétables dans divers domaines.
Nous sommes ainsi amenés à étudier une évolution de l’ensemble de satisfaction de contraintes XORSAT dans laquelle les interactions sont de portée finie. Ce nouvel ensemble s’interprète en champ moyen dans la limite de Kac. Dans une seconde limite où le rapport entre le nombre total de variables et la portée des interactions reste fixe, cet ensemble s’interprète comme un système de taille finie en champ moyen. L’étude à la fois analytique et numérique permet de mettre en évidence une divergence concrète de la longueur mosaïque ainsi que de présenter un problème de satisfiabilité possédant une interprétation réaliste. Nous avons aussi étudié un ensemble d’algorithmes approchés dans le domaine du codage. Certains problèmes de ce domaine possèdent une mémoire qui rend la complexité des algorithmes d’estimation exponentielle. Une interprétation en champ moyen de ces problèmes nous a permis d’obtenir des résultats probants quant à la réduction de la complexité algorithmique les concernant.
Abstract :
This thesis is devoted to the development and study of probabilistic models presenting spatial structure. The considered problems are as much part of statistical physics of disordered systems as they are of statistical inference in computer science. The spatial structure enables the introduction of concrete models directly interpreted in various fields.
We are led to study an evolution of the constraint satisfaction ensemble known as XORSAT in which interactions have a finite range. This new ensemble is interpreted in mean field through the use of the Kac limit. In a second limit where the ratio of the total number of variables to the interaction range is kept fixed, this ensemble is interpreted as finite sized system in mean field. The analytical and numerical studies led in parallel result in the observation in a concrete system of the mosaic length divergence as well as in the introduction of a satisfiability problem with a realistic interpretation. We have also studied a set of approximate algorithms in the field of coding. Some of the problems in this field possess a memory which result in rendering the complexity of estimation algorithms over these problems exponential. A mean field interpretation of these problems enables us to introduce reduced complexity algorithms.
RECRUTEMENT ACCES DIRECT
Le département de physique
Le Laboratoire de Physique de l’ENS 