Soutenance de thèse Louise Budzynski

La soutenance de thèse de Louise Budzynski aura lieu
le mardi 29 septembre à 16h
par visioconférence.
Sa thèse intitulée "Barrières algorithmiques dans les problèmes de satisfaction de contraintes" a été réalisée au Laboratoire de Physique de l’Ecole normale supérieure sous la direction de Guilhem Semerjian.

— > Lien de la visioconférence : https://global.gotomeeting.com/join/217463285 (Identifiant : 217-463-285)

La soutenance aura lieu également en présentiel en salle L367 - Département de Physique de l’ENS - 24 rue Lhomond 75005 PARIS

Résumé en français :

La complexité typique des Problèmes de Satisfaction de Contraintes (CSP) peut être étudiée à l’aide d’ensembles aléatoires de contraintes. On observe un phénomène de seuil quand la densité de contraintes augmente. En particulier à la transition de clustering, l’ensemble des solutions typiques se fracture en groupes de solutions séparés les uns des autres. Dans cette thèse nous introduisons un biais qui brise l’uniformité entre les solutions d’une instance de CSP, et nous étudions son effet sur la valeur du seuil de clustering. Nous étudions en particulier le problème de bicoloriage de $k$-hypergraphes. Pour de petites valeurs de $k$, nous montrons que ce biais peut augmenter la valeur du seuil de clustering, et que cela a un effet positif sur les performances de l’algorithme de Simulated Annealing pour la recherche de solutions d’une instance du problème de bicoloriage. Dans la limite où $k$ tend vers l’infini, nous calculons le développement asymptotique du seuil de clustering pour la mesure uniforme et pour une mesure biasée. Nous évaluons le gain obtenu avec cette implémentation du biais.

Résumé en anglais :

The typical complexity of Constraint Satisfaction Problems (CSP) can be studied using random ensembles of instances. One observes threshold phenomena when the density of constraints increases, in particular a clustering phase transition at which typical solutions shatter into disconnected components.
In this Ph.D., we introduce a bias that breaks the uniformity among solutions of a given instance of CSP, and look at the evolution of the clustering threshold under this bias, focusing on the bicoloring of $k$-uniform random hypergraphs.
For small values of $k$, we show that this bias can delay the clustering transition to higher densities of constraints, and that it has a positive impact on the performances of Simulated Annealing algorithm to find a solution for a given instance of the bicoloring problem.
In the large $k$ limit, we compute the asymptotic expansion of the clustering threshold for the uniform and the biased measure, and characterize the gain obtained with our implementation of the bias.