THÈSES 2011-2012

Vincent DELECROIX
(thème DAC)

Titre : Combinatoire et dynamique du flot de Teichmüller

Directeur de thèse : Arnaldo Nogueira

Rapporteurs : William Veech, Jean-Cristophe Yoccoz.

Jury : Pierre Arnoux, Pascal Hubert, Arnaldo Nogueira, Jean-Cristophe Yoccoz, Anton Zorich.

Date : 16 novembre 2011

Université d'inscription : Aix-Marseille II

Résumé : Ce travail de thèse porte sur la dynamique du flot linéaire des surfaces de translation et de sa re- normalisation par le flot de Teichmüller introduite par H. Masur et W. Veech en 1982. Une version combinatoire de cette renormalisation, l’induction de Rauzy sur les échanges d’intervalles, fût intro- duite auparavant par G. Rauzy en 1979. D’une part, nous faisons une étude combinatoire des classes de Rauzy qui forment une partition de l’ensemble des permutations irréductibles et interviennent dans l’algorithme d’induction de Rauzy. Nous donnons une formule pour la cardinalité de chaque classe. D’autre part, nous étudions un modèle de billard infini Z²-périodique dans le plan appelé le « vent dans les arbres » introduit dans une version stochastique par P. et T. Ehrenfest en 1912 et par J.Hardy et J.Weber en 1980 dans la version périodique. Nous construisons une famille de directions pour lesquelles le flot du billard est divergent donnant ainsi des exemples de Z²-cocycles divergents au-dessus d’échanges d’intervalles. De plus, nous démontrons que le taux polynomial de diffusion générique est 2/3 autrement dit que la distance maximale atteinte par une particule au temps t est de l’ordre de t^2/3.

Abstract: In this thesis, we study the dynamics of the linear flow of translation surfaces and its renormalization by the Teichmüller flow introduced by H.Masur and W.Veech in 1982. A combinatorial version of the renormalization, the Rauzy induction on interval exchange transformations, was introduced by G.Rauzy in 1979. First of all, we consider the combinatorics of Rauzy classes which form a partition of the set of irreducible permutations and are part of the Rauzy induction. In a second time, we consider an infinite Z²-periodic billiard in the plane called the wind-tree model. It was introduced in a stochastic version by P. and T.Ehrenfest in 1912 and in the periodic version by J. Hardy and J. Weber in 1980. We construct a family of directions for which the flow of the billiard is divergent and hence give examples of divergent Z²-cocycles over interval exchange transformations. Moreover, we prove that the polynomial rate of diffusion is generically 2/3. In other words, the maximal distance reached by a particule below time t has the order of t^2/3.

Fichier / File

( 1,96 Mo )

Meïli BARAGATTI
(thème STA)

Titre : Sélection bayésienne de variables et méthodes de type Parallel Tempering avec et sans vraisemblance

Directeur de thèse : Denys Pommeret

Rapporteurs : Nicolas Chopin, Jean-Michel Marin.

Jury : Christophe Abraham, Avner Bar-Hen, Sabrina Carpentier, Marc Chadeau-Hyam, Nicolas Chopin, Adeline Leclercq-Samson, Jean-Michel Marin, Denys Pommeret.

Date : 10 novembre 2011

Université d'inscription : Aix-Marseille II

Résumé : Cette thèse se décompose en deux parties. Dans un premier temps nous nous intéressons à la sélection bayésienne de variables dans un modèle probit mixte. L'objectif est de développer une méthode pour sélectionner quelques variables pertinentes parmi plusieurs dizaines de milliers tout en prenant en compte le design d'une étude, et en particulier le fait que plusieurs jeux de données soient fusionnés. Le modèle de régression probit mixte utilisé fait partie d'un modèle bayésien hiérarchique plus large et le jeu de données est considéré comme un effet aléatoire. Cette méthode est une extension de la méthode de Lee et al. [131]. La première étape consiste à spécifier le modèle ainsi que les distributions a priori, avec notamment l'utilisation de l'a priori conventionnel de Zellner (g-prior) pour le vecteur des coefficients associé aux effets fixes [238]. Dans une seconde étape, nous utilisons un algorithme Metropolis-within-Gibbs couplé à la grouping (ou blocking) technique de Liu [141] afin de surmonter certaines difficultés d'échantillonnage. Ce choix a des avantages théoriques et computationnels. La méthode développée est appliquée à des jeux de données microarray sur le cancer du sein. Cependant elle a une limite : la matrice de covariance utilisée dans le g-prior doit nécessairement être inversible. Or il y a deux cas pour lesquels cette matrice est singulière : lorsque le nombre de variables sélectionnées dépasse le nombre d'observations, ou lorsque des variables sont combinaisons linéaires d'autres variables. Nous proposons donc une modification de l'a priori de Zellner en y introduisant un paramètre de type ridge, ainsi qu'une manière de choisir les hyper-paramètres associés. L'a priori obtenu est un compromis entre le g-prior classique et l'a priori supposant l'indépendance des coefficients de régression, et se rapproche d'un a priori précédemment proposé par Gupta et Ibrahim [89].
Dans une seconde partie nous développons deux nouvelles méthodes MCMC basées sur des populations de chaînes. Dans le cas de modèles complexes ayant de nombreux paramètres, mais où la vraisemblance des données peut se calculer, l'algorithme Equi-Energy Sampler (EES) in- troduit par Kou et al. [118] est apparemment plus efficace que l'algorithme classique du Parallel Tempering (PT) introduit par Geyer [76]. Cependant, il est difficile d'utilisation lorsqu'il est couplé avec un échantillonneur de Gibbs, et nécessite un stockage important de valeurs. Nous proposons un algorithme combinant le PT avec le principe d'échanges entre chaînes ayant des niveaux d'énergie similaires dans le même esprit que l'EES. Cette adaptation appelée Parallel Tempering with Equi-Energy Moves (PTEEM) conserve l'idée originale qui fait la force de l'al- gorithme EES tout en assurant de bonnes propriétés théoriques et une utilisation facile avec un échantillonneur de Gibbs. Enfin, dans certains cas complexes l'inférence peut être difficile car le calcul de la vraisemblance des données s'avère trop coûteux, voire impossible. De nombreuses méthodes sans vraisemblance ont été développées. Par analogie avec le Parallel Tempering, nous proposons une méthode appe- lée ABC-Parallel Tempering, basée sur la théorie des MCMC, utilisant une population de chaînes et permettant des échanges entre elles.

Mots clefs : sélection bayésienne de variables, modèle probit mixte, a priori de Zellner, paramètre ridge, Monte Carlo Markov Chains, Parallel Tempering, Equi-Energy Sampler, Approximate Bayesian Computation, méthodes sans vraisemblance

Abstract: This thesis is divided into two main parts. In the first part, we propose a Bayesian variable selection method for probit mixed models. The objective is to select few relevant variables among tens of thousands while taking into account the design of a study, and in particular the fact that several datasets are merged together. The probit mixed model used is considered as part of a larger hierarchical Bayesian model, and the dataset is introduced as a random effect. The proposed method extends a work of Lee et al. [131]. The first step is to specify the model and prior distributions. In particular, we use the g-prior of Zellner [238] for the fixed regression coefficients. In a second step, we use a Metropolis-within-Gibbs algorithm combined with the grouping (or blocking) technique of Liu [141]. This choice has both theoritical and practical advantages. The method developed is applied to merged microarray datasets of patients with breast cancer. However, this method has a limit : the covariance matrix involved in the g-prior should not be singular. But there are two standard cases in which it is singular : if the number of observations is lower than the number of variables, or if some variables are linear combinations of others. In such situations we propose to modify the g-prior by introducing a ridge parameter, and a simple way to choose the associated hyper-parameters. The prior obtained is a compromise between the conditional independent case of the coefficient regressors and the automatic scaling advantage offered by the g-prior, and can be linked to the work of Gupta and Ibrahim [89].
In the second part, we develop two new population-based MCMC methods. In cases of complex models with several parameters, but whose likelihood can be computed, the Equi-Energy Sampler (EES) of Kou et al. [118] seems to be more efficient than the Parallel Tempering (PT) algorithm introduced by Geyer [76]. However it is difficult to use in combination with a Gibbs sampler, and it necessitates increased storage. We propose an algorithm combining the PT with the principle of exchange moves between chains with same levels of energy, in the spirit of the EES. This adaptation which we are calling Parallel Tempering with Equi-Energy Move (PTEEM) keeps the original idea of the EES method while ensuring good theoretical properties and a prac- tical use in combination with a Gibbs sampler. Then, in some complex models whose likelihood is analytically or computationally intractable, the inference can be difficult. Several likelihood-free methods (or Approximate Bayesian Computational Methods) have been developed. We propose a new algorithm, the Likelihood Free-Parallel Tempering, based on the MCMC theory and on a population of chains, by using an analogy with the Parallel Tempering algorithm.

Keywords: Bayesian variable selection, probit mixed model, Zellner g-prior, ridge parameter, Monte Carlo Markov Chains, Parallel Tempering, Equi-Energy Sampler, Approximate Bayesian Computation, Likelihood-Free methods

Fichier / File

( 2,04 Mo )

Christophe ARENE
(thème ATI)

Titre : Géométrie et arithmétique explicites des variétés abéliennes et applications à la cryptographie

Directeurs de thèse : David Kohel, Christophe Ritzenthaler

Rapporteurs : Sylvain Duquesne, Florian Hess.

Jury : Sylvain Duquesne, Florian Hess, Pierrick Gaudry, Laurent Imbert, David Kohel, Gilles Lachaud, Christophe Ritzenthaler.

Date : 27 septembre 2011

Université d'inscription : Aix-Marseille II

Résumé : Les principaux objets étudiés dans cette thèse sont les équations décrivant le morphisme de groupe sur une variété abélienne, plongée dans un espace projectif, et leurs applications en cryptographie. Notons g sa dimension et k son corps de définition. Ce mémoire est composé de deux parties. La première porte sur l’étude des courbes d’Edwards, un modèle pour les courbes elliptiques possédant un sous-groupe de points k-rationnels cyclique d’ordre 4, connues en cryptographie pour l’efficacité de leur loi d’addition et la possibilité qu’elle soit définie pour toute paire de points k-rationnels (loi d’addition k-complète). Nous en donnons une interprétation géométrique et en déduisons des formules explicites pour le calcul du couplage de Tate réduit sur courbes d’Edwards tordues, dont l’efficacité rivalise avec les modèles elliptiques couramment utilisés. Cette partie se conclut par la génération, spécifique au calcul de couplages, de courbes d’Edwards dont les tailles correspondent aux standards cryptographiques actuellement en vigueur. Dans la seconde partie nous nous intéressons à la notion de complétude introduite ci-dessus. Cette propriété est cryptographiquement importante car elle permet d’éviter des attaques physiques, comme les attaques par canaux cachés, sur des cryptosystèmes basés sur les courbes elliptiques ou hyperelliptiques. Un précédent travail de Lange et Ruppert, basé sur la cohomologie des fibrés en droite, permet une approche théorique des lois d’addition. Nous présentons trois résultats importants : tout d’abord nous généralisons un résultat de Bosma et Lenstra en démontrant que le morphisme de groupe ne peut être décrit par strictement moins de g+1 lois d’addition sur la clôture algébrique de k. Ensuite nous démontrons que si le groupe de Galois absolu de k est infini, alors toute variété abélienne peut être plongée dans un espace projectif de manière à ce qu’il existe une loi d’addition k-complète. De plus, l’utilisation des variétés abéliennes nous limitant à celles de dimension un ou deux, nous démontrons qu’une telle loi existe pour leur plongement projectif usuel. Finalement, nous développons un algorithme, basé sur la théorie des fonctions thêta, calculant celle-ci dans P¹⁵ sur la jacobienne d’une courbe de genre deux donnée par sa forme de Rosenhain. Il est désormais intégré au package AVIsogenies de Magma.

Mots clefs : courbes d’Edwards tordues, courbe elliptique, loi d’addition k-complète, couplage de Tate réduit, formules explicites, fibré en droite, plongement projectif, jacobienne d’une courbe de genre 2, fonctions thêta, thêta constantes

Abstract: The main objects we study in this PhD thesis are the equations describing the group morphism on an abelian variety, embedded in a projective space, and their applications in cryptograhy. We denote by g its dimension and k its field of definition. This thesis is built in two parts. The first one is concerned by the study of Edwards curves, a model for elliptic curves having a cyclic subgroup of k-rational points of order 4, known in cryptography for the efficiency of their addition law and the fact that it can be defined for any couple of k-rational points (k-complete addition law). We give the corresponding geometric interpretation and deduce explicit formulae to calculate the reduced Tate pairing on twisted Edwards curves, whose efficiency compete with currently used elliptic models. The part ends with the generation, specific to pairing computation, of Edwards curves with today’s cryptographic standard sizes. In the second part, we are interested in the notion of completeness introduced above. This property is cryptographically significant, indeed it permits to avoid physical attacks as side channel attacks, on elliptic – or hyperelliptic – curves cryptosystems. A preceeding work of Lange and Ruppert, based on cohomology of line bundles, brings a theoretic approach of addition laws. We present three important results: first of all we generalize a result of Bosma and Lenstra by proving that the group morphism can not be described by less than g + 1 addition laws on the algebraic closure of k. Next, we prove that if the absolute Galois group of k is infinite, then any abelian variety can be projectively embedded together with a k-complete addition law. Moreover, a cryptographic use of abelian varieties restricting us to the dimension one and two cases, we prove that such a law exists for their classical projective embedding. Finally, we develop an algorithm, based on the theory of theta functions, computing this addition law in P¹⁵ on the Jacobian of a genus two curve given in Rosenhain form. It is now included in AVIsogenies, a Magma package.

Keywords: twisted Edwards curves, elliptic curve, k-complete addition law, reduced Tate pairing, explicite formulae, line bundle, projective embedding, Jacobian of a genus 2 curve, theta functions, theta constants

Fichier / File

( 3,15 Mo )