Dans la limite "diluée" où les nombres d'arêtes et de sommets divergent de manière comparable, il est naturel d'espérer que divers invariants classiques en théorie des graphes seront essentiellement déterminés par la seule "géométrie locale" du graphe -- c'est à dire, informellement, par l'aspect d'une boule de petit rayon autour d'un "sommet typique". Cette heuristique a pour origine l'étude des systèmes de particules en physique statistique, où sous certaines conditions, les contributions microscopiques provenant de sites suffisamment éloignés peuvent être considérées comme mutuellement indépendantes dans le calcul des grandeurs macroscopiques fondamentales du système. Mathématiquement, cette précieuse absence d'intéractions à longue portée peut se décrire rigoureusement à l'aide d'une propriété topologique : la continuité de l'invariant considéré vis-à-vis de la convergence locale faible des graphes. Tout invariant pour lequel on peut établir une telle continuité admettra aussitôt une limite déterministe le long de la plupart des suites de graphes aléatoires classiques, et pourra être efficacement approximé par des algorithmes locaux et distribués, indépendamment de la taille totale du système. Dans cette thèse, nous établissons la continuité de quatre invariants de graphes qui jouent un rôle essentiel en théorie comme dans les applications : la distribution spectrale empirique, la dimension du noyau de la matrice d'adjacence, la taille d'un couplage maximum, et le polynôme énumérant certaines familles de sous-graphes couvrants. Plus précisément, nous montrons qu'il existe une unique manière localement cohérente d'étendre chacune de ces notions aux limites locales faibles de graphes finis, et que ce prolongement est continu. Pour les modèles de graphes aléatoires classiques, les équations de cohérence locale se simplifient en une équation aux distributions que nous résolvons explicitement. Cela conduit à de nouvelles formules asymptotiques, ainsi qu'à la simplification, l'unification et la généralisation de divers résultats jusqu'alors isolés.

Les problèmes d'optimisation et de satisfaction de contraintes sur des ensembles de variables discrètes sont l'objet principal de la complexité algorithmique. Ces problèmes ont récemment bénéficié des outils et des concepts de la physique des systèmes désordonnés, à la fois théoriquement et algorithmiquement. En particulier, il a été suggéré que les difficultés pratiques soulevées par certaines instances dures de problèmes d'optimisation sont liées à la structure fragmentée de leur espace de solutions, qui rappelle une phase vitreuse. Parallèlement, les codes de correction d'erreur de pointe, qui peuvent être ramenés à des problèmes d'optimisation, reposent sur la séparabilité de leurs messages afin d'assurer une communication fiable. L'objet de cette thèse est d'explorer, dans un cadre commun, cette relation entre les propriétés d'inférence et l'organisation géométrique, dans les problèmes issus de la complexité algorithmique et de la théorie de l'information.<br /><br />Après une introduction physique des problèmes et des concepts liés aux domaines sus-évoqués, les méthodes de passage de messages, basées sur l'approximation de Bethe, sont introduites. Ces méthodes sont utiles d'un point de vue physique, car elle permettent d'étudier les propriétés thermodynamiques d'ensemble d'instances aléatoires. Elles sont également utiles pour l'inférence. L'analyse de spectres de distances est ensuite effectuée à l'aide de méthodes combinatoires et de passage de messages, et mises à profit afin de prouver et l'existence de la fragmentation dans les problèmes de satisfaction de contraintes, et d'en étudier les aspects importants.

Durant cette thèse, je me suis intéressé à deux thématiques générales qui peuvent être explorées dans des systèmes d'atomes froids : d'une part, la dynamique hors-équilibre d'un système quantique isolé, et d'autre part l'influence du désordre sur un système fortement corrélé à basse température. Dans un premier temps, nous avons développé une méthode de champ moyen, qui permet de résoudre la dynamique unitaire dans un modèle à géométrie particulière, le réseau complètement connecté. Cette approche permet d'établir une correspondance entre la dynamique unitaire du système quantique et des équations du mouvement classique. Nous avons mis à profit cette méthode pour étudier le phénomène de transition dynamique qui se signale, dans des modèles de champ moyen, par une singularité des observables aux temps longs, en fonction des paramètres initiaux ou finaux de la trempe. Nous avons montré l'existence d'une transition dynamique quantique dans les modèle de Bose-Hubbard, d'Ising en champ transverse et le modèle de Jaynes-Cummings. Ces résultats confirment l'existence d'un lien fort entre la présence d'une transition de phase quantique et d'une transition dynamique.Dans un second temps, nous avons étudié un modèle de théorie des champs relativiste avec symétrie O(N) afin de comprendre l'influence des fluctuations sur ces singularités. À l'ordre dominant en grand N, nous avons montré que la transition dynamique s'apparente à un phénomène critique. En effet, à la transition dynamique, les fonctions de corrélations suivent une loi d'échelle à temps égaux et à temps arbitraires. Il existe également une longueur caractéristique qui diverge à l'approche du point de transition. D'autre part, il apparaît que le point fixe admet une interprétation en terme de particules sans masse se propageant librement. Enfin, nous avons montré que la dynamique asymptotique au niveau du point fixe s'apparente à celle d'une trempe d'un état symétrique dans la phase de symétrie brisée. Le troisième volet de cette thèse apporte des éléments nouveaux pour la compréhension du diagramme des phases du modèle de Bose-Hubbard en présence de désordre. Pour ce faire,nous avons utilisé et étendu la méthode de la cavité quantique en champ moyen de Ioffe et Mézard, qui doit être utilisée avec la méthode des répliques. De cette manière, il est possible d'obtenir des résultats analytiques pour les exposants des lois de probabilité de la susceptibilité.Nos résultats indiquent que dans les différents régimes de la transition de phase de superfluide vers isolant, les lois d'échelle conventionnelles sont tantôt applicables, tantôt remplacées par une loi d'activation. Enfin, les exposants critiques varient continûment à la transition conventionnelle.

Dans les dernières années, plusieurs problèmes ont été étudiés à l'interface entre la physique statistique et l'informatique. La raison étant que, souvent, ces problèmes peuvent être réinterprétés dans le langage de la physique des systèmes désordonnés, où un grand nombre de variables interagit à travers champs locales qui dépendent de l'état du quartier environnant. Parmi les nombreuses applications de l'optimisation combinatoire le routage optimal sur les réseaux de communication est l'objet de la première partie de la thèse. Nous allons exploiter la méthode de la cavité pour formuler des algorithmes efficaces de type ‘’message-passing’’ et donc résoudre plusieurs variantes du problème grâce à sa mise en œuvre numérique. Dans un deuxième temps, nous allons décrire un modèle pour approcher la version dynamique de la méthode de la cavité, ce qui permet de diminuer la complexité du problème de l'exponentielle de polynôme dans le temps. Ceci sera obtenu en utilisant le formalisme de ‘’Matrix Product State’’ de la mécanique quantique.Un autre sujet qui a suscité beaucoup d'intérêt en physique statistique de processus dynamiques est la marche aléatoire sur les réseaux. La théorie a été développée depuis de nombreuses années dans le cas que la topologie dessous est un réseau de dimension d. Au contraire le cas des réseaux aléatoires a été abordé que dans la dernière décennie, laissant de nombreuses questions encore ouvertes pour obtenir des réponses. Démêler plusieurs aspects de ce thème fera l'objet de la deuxième partie de la thèse. En particulier, nous allons étudier le nombre moyen de sites distincts visités au cours d'une marche aléatoire et caractériser son comportement en fonction de la topologie du graphe. Enfin, nous allons aborder les événements rares statistiques associées aux marches aléatoires sur les réseaux en utilisant le ‘’Large deviations formalism’’. Deux types de transitions de phase dynamiques vont se poser à partir de simulations numériques. Nous allons conclure décrivant les principaux résultats d'une œuvre indépendante développée dans le cadre de la physique hors de l'équilibre. Un système résoluble en deux particules browniens entouré par un bain thermique sera étudiée fournissant des détails sur une interaction à médiation par du bain résultant de la présence du bain. / In the last years several problems been studied at the interface between statistical physics and computer science. The reason being that often these problems can be reinterpreted in the language of physics of disordered systems, where a big number of variables interacts through local fields dependent on the state of the surrounding neighborhood. Among the numerous applications of combinatorial optimisation the optimal routing on communication networks is the subject of the first part of the thesis. We will exploit the cavity method to formulate efficient algorithms of type message-passing and thus solve several variants of the problem through its numerical implementation. At a second stage, we will describe a model to approximate the dynamic version of the cavity method, which allows to decrease the complexity of the problem from exponential to polynomial in time. This will be obtained by using the Matrix Product State formalism of quantum mechanics. Another topic that has attracted much interest in statistical physics of dynamic processes is the random walk on networks. The theory has been developed since many years in the case the underneath topology is a d-dimensional lattice. On the contrary the case of random networks has been tackled only in the past decade, leaving many questions still open for answers. Unravelling several aspects of this topic will be the subject of the second part of the thesis. In particular we will study the average number of distinct sites visited during a random walk and characterize its behaviour as a function of the graph topology. Finally, we will address the rare events statistics associated to random walks on networks by using the large-deviations formalism. Two types of dynamic phase transitions will arise from numerical simulations, unveiling important aspects of these problems. We will conclude outlining the main results of an independent work developed in the context of out-of-equilibrium physics. A solvable system made of two Brownian particles surrounded by a thermal bath will be studied providing details about a bath-mediated interaction arising for the presence of the bath.

L'optimisation est un concept fondamental dans beaucoup de domaines scientifiques comme l'informatique, la théorie de l'information, les sciences de l'ingénieur et la physique statistique, ainsi que pour la biologie et les sciences sociales. Un problème d'optimisation met typiquement en jeu un nombre important de variables et une fonction de coût qui dépend de ces variables. La classe des problèmes NP-complets est particulièrement difficile, et il est communément admis que, dans le pire des cas, un nombre d'opérations exponentiel dans la taille du problème est nécessaire pour minimiser la fonction de coût. Cependant, même ces problèmes peuveut être faciles à résoudre en pratique. La question principale considérée dans cette thèse est comment reconnaître si un problème de satisfaction de contraintes NP-complet est "typiquement" difficile et quelles sont les raisons pour cela ? Nous suivons une approche inspirée par la physique statistique des systèmes désordonnés, en particulier la méthode de la cavité développée originalement pour les systèmes vitreux. Nous décrivons les propriétés de l'espace des solutions dans deux des problèmes de satisfaction les plus étudiés : la satisfiabilité et le coloriage aléatoire. Nous suggérons une relation entre l'existence de variables dites "gelées" et la difficulté algorithmique d'un problème donné. Nous introduisons aussi une nouvelle classe de problèmes, que nous appelons "problèmes verrouillés", qui présentent l'avantage d'être à la fois facilement résoluble analytiquement, du point de vue du comportement moyen, mais également extrêmement difficiles du point de vue de la recherche de solutions dans un cas donné.

Durant cette thèse, je me suis intéressé à deux thématiques générales qui peuvent être explorées dans des systèmes d’atomes froids : d’une part, la dynamique hors-équilibre d’un système quantique isolé, et d’autre part l’influence du désordre sur un système fortement corrélé à basse température. Dans un premier temps, nous avons développé une méthode de champ moyen, qui permet de résoudre la dynamique unitaire dans un modèle à géométrie particulière, le réseau complètement connecté. Cette approche permet d’établir une correspondance entre la dynamique unitaire du système quantique et des équations du mouvement classique. Nous avons mis à profit cette méthode pour étudier le phénomène de transition dynamique qui se signale, dans des modèles de champ moyen, par une singularité des observables aux temps longs, en fonction des paramètres initiaux ou finaux de la trempe. Nous avons montré l’existence d’une transition dynamique quantique dans les modèle de Bose-Hubbard, d’Ising en champ transverse et le modèle de Jaynes-Cummings. Ces résultats confirment l’existence d’un lien fort entre la présence d’une transition de phase quantique et d’une transition dynamique.Dans un second temps, nous avons étudié un modèle de théorie des champs relativiste avec symétrie O(N) afin de comprendre l’influence des fluctuations sur ces singularités. À l’ordre dominant en grand N, nous avons montré que la transition dynamique s’apparente à un phénomène critique. En effet, à la transition dynamique, les fonctions de corrélations suivent une loi d’échelle à temps égaux et à temps arbitraires. Il existe également une longueur caractéristique qui diverge à l’approche du point de transition. D’autre part, il apparaît que le point fixe admet une interprétation en terme de particules sans masse se propageant librement. Enfin, nous avons montré que la dynamique asymptotique au niveau du point fixe s’apparente à celle d’une trempe d’un état symétrique dans la phase de symétrie brisée. Le troisième volet de cette thèse apporte des éléments nouveaux pour la compréhension du diagramme des phases du modèle de Bose-Hubbard en présence de désordre. Pour ce faire,nous avons utilisé et étendu la méthode de la cavité quantique en champ moyen de Ioffe et Mézard, qui doit être utilisée avec la méthode des répliques. De cette manière, il est possible d’obtenir des résultats analytiques pour les exposants des lois de probabilité de la susceptibilité.Nos résultats indiquent que dans les différents régimes de la transition de phase de superfluide vers isolant, les lois d’échelle conventionnelles sont tantôt applicables, tantôt remplacées par une loi d’activation. Enfin, les exposants critiques varient continûment à la transition conventionnelle. / The fast progress of cold atoms experiments in the last decade has allowed to explore new aspects of strongly correlated systems. This thesis deals with two such general themes: the out of equilibrium dynamics of closed quantum systems, and the impact of disorder on strongly correlated bosons at zero temperature. Among the different questions about out of equilibrium dynamics, the phenomenon of dynamical transition is still lacking a complete understanding. The transition is typically signalled, in mean-field, by a singular behaviour of observables as a function of the parameters of the quench. In this thesis, a mean field method is developed to give evidence of a strong link between the quantum phase transition at zero temperature and the dynamical transition. We then study using field theory techniques a relativistic O($N$) model, and show that the dynamical transition bears similarities with a critical phenomenon. In this context, the dynamical transition also appears to be formally related to the dynamics of symmetry breaking. The second part of this thesis is about the disordered Bose-Hubbard model and the nature of its phase transitions. We use and extend the cavity mean field method, introduced by Ioffe and Mezard to obtain analytical results from the quantum cavity method and the replica trick. We find that the conventional transition, with power law scaling, is changed into an activated scaling in some regions of the phase diagram. Furthermore, the critical exponents are continuously varying along the conventional transition. These intriguing properties call for further investigations using different methods.

Cette thèse porte principalement sur l'équilibrage de charge dans de grands graphes aléatoires. En informatique, un problème d'équilibrage de charge survient lorsque différentes tâches ont besoin d'accéder à un même ensemble de points de ressources. Il faut alors décider quelles ressources spécifiques seront allouées à quelles tâches. Suivant le contexte, les notions de "tâche" et de "ressource" peuvent avoir différentes interprétations. Afin de prendre des exemples concrets, on se concentrera sur deux applications en particulier: - un système de hachage à choix multiples (plus précisément, le "cuckoo hashing"). L'objectif est ici d'allouer des cellules d'un tableau à des objets, afin de pouvoir ensuite vérifier facilement la présence d'un objet et récupérer les données associées. Les tâches sont liées aux objets à stocker, et les ressources sont les cellules du tableau. - un réseau de distribution de contenu distribué, au sens où les contenus peuvent être stockés sur une multitude de petits serveurs aux capacités individuelles très limitées. Ici, les tâches sont des demandes de téléchargement (ou requêtes) pour un contenu et les ressources sont liées aux serveurs et à la façon dont leurs espaces de stockage sont utilisés. Le problème d'équilibrage de charge consiste à décider quel serveur va servir quelle requête. Les contraintes locales portant sur chaque ressource (en quelle quantité est-elle disponible et pour quelles tâches est-elle convenable?) ainsi que la charge de travail associée avec chaque tâche peuvent être représentées efficacement sur un graphe biparti, avec des contraintes de capacité sur ses sommets et ses arêtes. De plus, en pratique, les systèmes considérés sont souvent de très grande taille (avec parfois des milliers de tâches et de points de ressources différents) et relativement aléatoires (que ce soit par choix ou une conséquence de leur grande taille). Une modélisation à l'aide de grands graphes aléatoires est donc souvent pertinente. L'ensemble des solutions envisageables pour un problème d'équilibrage de charge donné étant vaste, il est primordial de commencer par déterminer des bornes sur les performances que l'on peut espérer. Ainsi, on considérera dans un premier temps une solution optimale du problème (même si elle ne serait pas réalisable avec des contraintes pratiques). Les performances d'une telle solution peuvent être obtenues en étudiant les appariements de taille maximum dans un grand graphe aléatoire, ce que l'on réalisera à l'aide de la méthode de la cavité. Cette méthode vient de l'étude des systèmes désordonnés en physique statistique, et on s'attachera ici à l'appliquer de manière rigoureuse dans le cadre que l'on considère. Dans le contexte du cuckoo hashing, les résultats obtenus permettent de calculer le seuil sur la charge du système (le nombre d'objets à insérer par rapport à la taille du tableau) en-dessous duquel on peut construire une table de hachage correcte avec grande probabilité dans un grand système, et également de traiter de manière similaire de variantes de la méthode de hachage basique qui tentent de diminuer la quantité d'aléa nécessaire au système. Au-delà du problème d'équilibrage de charge, dans le cadre des réseaux de distributions de contenu distribués, un second problème se pose: comment décider quel contenu stocker et en quelle quantité, autrement dit comment répliquer les contenus? On appelle ce second problème un problème d'allocation de ressources. A nouveau, l'étude déjà réalisée permet de quantifier l'efficacité d'une politique de réplication fixée en supposant que la politique d'équilibrage de charge fonctionne de manière optimale. Il reste cependant à optimiser la politique de réplication de contenus utilisée, ce que l'on effectue dans un régime où l'espace de stockage disponible au niveau de chaque serveur est important par rapport à la taille d'un contenu. Finalement, afin de quantifier maintenant les performances minimales atteignables en pratique, on s'intéressera aux mêmes questions lorsque la politique d'équilibrage de charge utilisée est un simple algorithme glouton. Cette étude est réalisée à l'aide d'approximations de champs moyen. On utilisera également les résultats obtenus afin de concevoir des politiques de réplication de contenus adaptatives.