Soutenances de Thèses 2008

Vendredi 20 juin 2008 à 10h30
Salle des Conseils de l’IPN (Orsay)
Bât.100

Lenka Zdeborová

Statistical Physics of Hard Optimisation Problems

Optimization is fundamental in many areas of science, from computer science and information theory to engineering and statistical physics, as well as to biology or social sciences. It typically involves a large number of variables and a cost function depending on these variables. Optimization problems in the NP-complete class are particularly difficult, it is believed that the number of operations required to minimize the cost function is in the most difficult cases exponential in the system size. However, even in an NP-complete problem the practically arising instances might, in fact, be easy to solve. The principal question we address in this thesis is: How to recognize if an NP-complete constraint satisfaction problem is typically hard and what are the main reasons for this? We adopt approaches from the statistical physics of disordered systems, in particular the cavity method developed originally to describe glassy systems. We describe new properties of the space of solutions in two of the most studied constraint satisfaction problems - random satisfiability and random graph coloring. We suggest a relation between the existence of the so-called frozen variables and the algorithmic hardness of a problem. Based on these insights, we introduce a new class of problems which we named "locked" constraint satisfaction, where the statistical description is easily solvable, but from the algorithmic point of view they are even more challenging than the canonical satisfiability.


Mardi 23 septembre 2008 à 11h00
Salle des Conseils de l'IPN (Orsay)
Bât. 100

Rémy Dubertrand

Deux applications du chaos quantique : étude des fonctions aléatoires via SLE et description de cavités diélectriques.

Nous avons utilisé les techniques bien connues en chaos quantiques pour étudier les cavités diélectriques. Ces systèmes ouverts sont actuellement au centre de nombreux travaux expérimentaux. Nous montrerons comment nous pouvons donner des formules pour décrire les résonances d'un tel système dans le cas d'une forme circulaire. Puis nous étendrons notre étude à de petites déformations de cette cavité. Enfin nous décrirons les travaux récents que nous avons menés pour définir une formule de trace pour ces systèmes. Nous donnerons de nombreux exemples où nous avons pu vérifier nos prévisions numériquement.

Mercredi 17 décembre 2008 à 14h30
Salle des Conseils de l'IPN (Orsay)
Bât. 100

Maria Colomé Tatché

Effets de taille finie et dynamique dans les systèmes intégrables unidimensionnels.

De nombreux systèmes physiques peuvent être décrits par des modèles unidimensionnels. C'est en particulier le cas de certains gaz d'atomes ultrafroids: dans les bonnes conditions, lorsqu'ils sont confinés dans des pièges unidimensionnels, leur dynamique a lieu suivant une seule dimension spatiale. Au cours de ma thèse de doctorat je me suis intéressée à l'étude de quelques aspects des systèmes intégrables à une dimension. Je présente d'abord une étude de l'état fondamental d'un système unidimensionnel de fermions à deux composantes en interaction de contact répulsive, dans un piège harmonique. Ensuite j´étudie des corrections au gap du spectre d'excitations pour le modèle d'Hubbard unidimensionnel avec attraction locale, dues aux effets de taille finie. Finalement, j'étudie la réponse d'un système fortement excité à la modulation temporelle de la valeur de la constante d'interaction entre les atomes. Je considère à cet effet le modèle intégrable de Lieb-Liniger et le modèle non-intégrable d'un gaz de fermions avec une impureté mobile.