Louise Budzynski

Barrières algorithmiques dans les problèmes aléatoires de satisfaction de contraintes: 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 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 biaisée. Nous évaluons le gain obtenu avec cette implémentation du biais.

We study a system of y=2 coupled copies of a well-known constraint satisfaction problem (random hypergraph bicoloring) to examine how the ferromagnetic coupling between the copies affects the properties of the solution space. We solve the replicated model by applying the cavity method to the supervariables that take 2^{y} values. Our results show that a coupling of strength γ between the copies decreases the clustering threshold α_{d}(γ), at which typical solutions shatter into disconnected components, therefore preventing numerical methods such as Monte Carlo Markov chains from reaching equilibrium in polynomial time. This result needs to be reconciled with the observation that, in models with coupled copies, denser regions of the solution space should be more accessible. Additionally, we observe a change in the nature of the clustering phase transition, from discontinuous to continuous, in a wide γ range. We investigate how the coupling affects the behavior of the belief propagation (BP) algorithm on finite-size instances and find that BP convergence is significantly impacted by the continuous transition. These results highlight the importance of better understanding algorithmic performance at the clustering transition and call for further exploration into the optimal use of reweighting strategies designed to enhance algorithmic performance.

In Bayesian inference, computing the posterior distribution from the data is typically a nontrivial problem, which usually requires approximations such as mean-field approaches or numerical methods, like the Monte Carlo Markov chain. Being a high-dimensional distribution over a set of correlated variables, the posterior distribution can undergo the notorious replica symmetry-breaking transition. When that happens, several mean-field methods and virtually every Monte Carlo scheme cannot provide a reasonable approximation to the posterior and its marginals. Replica symmetry is believed to be guaranteed whenever the data are generated with known prior and likelihood distributions, namely under the so-called Nishimori conditions. In this paper, we break this belief by providing a counterexample showing that under the Nishimori conditions, replica symmetry breaking arises. Introducing a simple, geometrical model that can be thought of as a patient-zero retrieval problem in a highly infectious regime of the epidemic Susceptible-Infectious model, we show that under the Nishimori conditions there is evidence of replica symmetry breaking. We achieve this result by computing the instability of the replica symmetric cavity method toward the one-step replica symmetry-broken phase. The origin of this phenomenon-replica symmetry breaking under the Nishimori conditions-is likely due to the correlated disorder appearing in the epidemic models.

We investigate the information-theoretical limits of inference tasks in epidemic spreading on graphs in the thermodynamic limit. The typical inference tasks consist in computing observables of the posterior distribution of the epidemic model given observations taken from a ground-truth (sometimes called planted) random trajectory. We can identify two main sources of quenched disorder: the graph ensemble and the planted trajectory. The epidemic dynamics however induces nontrivial long-range correlations among individuals' states on the latter. This results in nonlocal correlated quenched disorder which unfortunately is typically hard to handle. To overcome this difficulty, we divide the dynamical process into two sets of variables: a set of stochastic independent variables (representing transmission delays), plus a set of correlated variables (the infection times) that depend deterministically on the first. Treating the former as quenched variables and the latter as dynamic ones, computing disorder average becomes feasible by means of the replica-symmetric cavity method. We give theoretical predictions on the posterior probability distribution of the trajectory of each individual, conditioned to observations on the state of individuals at given times, focusing on the susceptible infectious (SI) model. In the Bayes-optimal condition, i.e., when true dynamic parameters are known, the inference task is expected to fall in the replica-symmetric regime. We indeed provide predictions for the information theoretic limits of various inference tasks, in form of phase diagrams. We also identify a region, in the Bayes-optimal setting, with strong hints of replica-symmetry breaking. When true parameters are unknown, we show how a maximum-likelihood procedure is able to recover them with mostly unaffected performance.

The alignment of biological sequences such as DNA, RNA, and proteins, is one of the basic tools that allow to detect evolutionary patterns, as well as functional or structural characterizations between homologous sequences in different organisms. Typically, state-of-the-art bioinformatics tools are based on profile models that assume the statistical independence of the different sites of the sequences. Over the last years, it has become increasingly clear that homologous sequences show complex patterns of long-range correlations over the primary sequence as a consequence of the natural evolution process that selects genetic variants under the constraint of preserving the functional or structural determinants of the sequence. Here, we present an alignment algorithm based on message passing techniques that overcomes the limitations of profile models. Our method is based on a perturbative small-coupling expansion of the free energy of the model that assumes a linear chain approximation as the zeroth-order of the expansion. We test the potentiality of the algorithm against standard competing strategies on several biological sequences.