Properties and algorithms of the (n, k)-star graphs

The (n, k)-star interconnection network was proposed in 1995 as an attractive alternative to the n-star topology in parallel computation. The (n, k )-star has significant advantages over the n-star which itself was proposed as an attractive alternative to the popular hypercube. The major advantage of the (n, k )-star network is its scalability, which makes it more flexible than the n-star as an interconnection network. In this thesis, we will focus on finding graph theoretical properties of the (n, k )-star as well as developing parallel algorithms that run on this network. The basic topological properties of the (n, k )-star are first studied. These are useful since they can be used to develop efficient algorithms on this network. We then study the (n, k )-star network from algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms for basic communication, prefix computation, and sorting, etc. A literature review of the state-of-the-art in relation to the (n, k )-star network as well as some open problems in this area are also provided.

Properties and algorithms of the (n, k)-arrangement graphs

The (n, k)-arrangement interconnection topology was first introduced in 1992. The (n, k )-arrangement graph is a class of generalized star graphs. Compared with the well known n-star, the (n, k )-arrangement graph is more flexible in degree and diameter. However, there are few algorithms designed for the (n, k)-arrangement graph up to present. In this thesis, we will focus on finding graph theoretical properties of the (n, k)- arrangement graph and developing parallel algorithms that run on this network. The topological properties of the arrangement graph are first studied. They include the cyclic properties. We then study the problems of communication: broadcasting and routing. Embedding problems are also studied later on. These are very useful to develop efficient algorithms on this network. We then study the (n, k )-arrangement network from the algorithmic point of view. Specifically, we will investigate both fundamental and application algorithms such as prefix sums computation, sorting, merging and basic geometry computation: finding convex hull on the (n, k )-arrangement graph. A literature review of the state-of-the-art in relation to the (n, k)-arrangement network is also provided, as well as some open problems in this area.

Properties and algorithms of the hyper-star graph and its related graphs

The hyper-star interconnection network was proposed in 2002 to overcome the drawbacks of the hypercube and its variations concerning the network cost, which is defined by the product of the degree and the diameter. Some properties of the graph such as connectivity, symmetry properties, embedding properties have been studied by other researchers, routing and broadcasting algorithms have also been designed. This thesis studies the hyper-star graph from both the topological and algorithmic point of view. For the topological properties, we try to establish relationships between hyper-star graphs with other known graphs. We also give a formal equation for the surface area of the graph. Another topological property we are interested in is the Hamiltonicity problem of this graph. For the algorithms, we design an all-port broadcasting algorithm and a single-port neighbourhood broadcasting algorithm for the regular form of the hyper-star graphs. These algorithms are both optimal time-wise. Furthermore, we prove that the folded hyper-star, a variation of the hyper-star, to be maixmally fault-tolerant.

Square Root Finding In Graphs

Abstract: Root and root finding are concepts familiar to most branches of mathematics. In graph theory, H is a square root of G and G is the square of H if two vertices x,y have an edge in G if and only if x,y are of distance at most two in H. Graph square is a basic operation with a number of results about its properties in the literature. We study the characterization and recognition problems of graph powers. There are algorithmic and computational approaches to answer the decision problem of whether a given graph is a certain power of any graph. There are polynomial time algorithms to solve this problem for square of graphs with girth at least six while the NP-completeness is proven for square of graphs with girth at most four. The girth-parameterized problem of root fining has been open in the case of square of graphs with girth five. We settle the conjecture that recognition of square of graphs with girth 5 is NP-complete. This result is providing the complete dichotomy theorem for square root finding problem.

Properties and Algorithms of the KCube Graphs

The KCube interconnection topology was rst introduced in 2010. The KCube graph is a compound graph of a Kautz digraph and hypercubes. Compared with the at- tractive Kautz digraph and well known hypercube graph, the KCube graph could accommodate as many nodes as possible for a given indegree (and outdegree) and the diameter of interconnection networks. However, there are few algorithms designed for the KCube graph. In this thesis, we will concentrate on nding graph theoretical properties of the KCube graph and designing parallel algorithms that run on this network. We will explore several topological properties, such as bipartiteness, Hamiltonianicity, and symmetry property. These properties for the KCube graph are very useful to develop efficient algorithms on this network. We will then study the KCube network from the algorithmic point of view, and will give an improved routing algorithm. In addition, we will present two optimal broadcasting algorithms. They are fundamental algorithms to many applications. A literature review of the state of the art network designs in relation to the KCube network as well as some open problems in this field will also be given.

Approches algorithmiques pour l’inférence d’histoires de duplication en tandem avec inversions et délétions pour des familles multigéniques

[Français] Une fraction importante des génomes eucaryotes est constituée de Gènes Répétés en Tandem (GRT). Un mécanisme fondamental dans l’évolution des GRT est la recombinaison inégale durant la méiose, entrainant la duplication locale (en tandem) de segments chromosomiques contenant un ou plusieurs gènes adjacents. Différents algorithmes ont été proposés pour inférer une histoire de duplication en tandem pour un cluster de GRT. Cependant, leur utilisation est limitée dans la pratique, car ils ne tiennent pas compte d’autres événements évolutifs pourtant fréquents, comme les inversions, les duplications inversées et les délétions. Cette thèse propose différentes approches algorithmiques permettant d’intégrer ces événements dans le modèle de duplication en tandem classique. Nos contributions sont les suivantes: • Intégrer les inversions dans un modèle de duplication en tandem simple (duplication d’un gène à la fois) et proposer un algorithme exact permettant de calculer le nombre minimal d’inversions s’étant produites dans l’évolution d’un cluster de GRT. • Généraliser ce modèle pour l’étude d’un ensemble de clusters orthologues dans plusieurs espèces. • Proposer un algorithme permettant d’inférer l’histoire évolutive d’un cluster de GRT en tenant compte des duplications en tandem, duplications inversées, inversions et délétions de segments chromosomiques contenant un ou plusieurs gènes adjacents.

Nutrition et état de santé : études paléochimique et paléopathologique de la population exhumée du cimetière protestant Saint-Matthew, ville de Québec, Canada (1771-1860)

Quatre-vingt-quinze squelettes humains issus des fouilles archéologiques du cimetière protestant Saint-Matthew (ville de Québec, 1771-1860) ont été étudiés en associant deux aspects de la paléonutrition : la paléochimie et la paléopathologie. Le but de cette recherche est d’explorer la relation entre nutrition et état de santé pour cette population préindustrielle. Des informations directes sur l’alimentation ont été recueillies par l’analyse des isotopes stables du carbone et de l’azote du collagène des os, et des informations indirectes ont été obtenues par une quantification de l’état de santé des individus. Les méthodes paléopathologiques utilisées sont celles de l’« indice de santé » (Steckel et al., 2002) pour la comparaison interpopulationnelle, puis des méthodes comprenant des degrés de sévérité plus précis afin d’étudier les variations intrapopulationnelles. L’analyse de ces données atteste d’un état de santé relativement mauvais par comparaison avec d’autres groupes nord-américains contemporains, malgré une alimentation similaire. Des différences alimentaires ont été observées en fonction des données paléodémographiques (âge, sexe), mettant notamment en évidence une variabilité temporelle dans la réalisation du processus de sevrage. De plus, un régime alimentaire moins riche en ressources C4 (maïs, sucre de canne) et en ressources animales (viande, poissons, produits laitiers) a été constaté pour les enfants entre 2 et 7 ans par rapport aux individus plus vieux. Enfin, une relation possible entre la sévérité de certaines pathologies (cribra orbitalia et périostite) et la consommation des ressources alimentaires en C4 et/ou marines et riches en protéines a été observée.

Computational prediction of neural progenitor cell fates

Understanding how stem and progenitor cells choose between alternative cell fates is a major challenge in developmental biology. Efforts to tackle this problem have been hampered by the scarcity of markers that can be used to predict cell division outcomes. Here we present a computational method, based on algorithmic information theory, to analyze dynamic features of living cells over time. Using this method, we asked whether rat retinal progenitor cells (RPCs) display characteristic phenotypes before undergoing mitosis that could foretell their fate. We predicted whether RPCs will undergo a self-renewing or terminal division with 99% accuracy, or whether they will produce two photoreceptors or another combination of offspring with 87% accuracy. Our implementation can segment, track and generate predictions for 40 cells simultaneously on a standard computer at 5 min per frame. This method could be used to isolate cell populations with specific developmental potential, enabling previously impossible investigations.

Immigration et alimentation à Montréal aux XVIIe et XVIIIe siècles : essai d’interprétation à partir d’analyses isotopiques sur des populations archéologiques

Afin d’étudier l’influence de la migration sur l’alimentation à Montréal aux XVIIe et XVIIIe siècles, 64 individus de la collection du cimetière Notre-Dame, daté de 1691 à 1796, ont fait l’objet d’analyses ostéologiques et isotopiques. Les analyses isotopiques ont portées sur le carbone (d13C) et l’azote (d15N) du collagène des os, ainsi que sur le d13C et l’oxygène (d18O) du carbonate de l’apatite des os et des dents (prémolaires et troisièmes molaires). Le d18O des dents a permis de définir approximativement trois régions d’origine (région de Montréal, région enrichie en 18O (i.e. Acadie, Louisiane, Nouvelle-Angleterre, France, Antilles et Afrique) et région appauvrie en 18O (intérieur des terres et plus au nord) pour 58 individus, et sept possibles parcours migratoire (N=27). Plus de la moitié de l’échantillon est composé d’individus possiblement natifs de Montréal (55 %). De plus, les résultats indiquent que les gens étaient peu mobiles avant l’âge de 16 ans. Toutefois, 12 individus ont entrepris des déplacements entre 7 et 16 ans, majoritairement d’un environnement enrichi vers Montréal (N=5) ou de Montréal vers une région appauvrie (N=5). L’âge de recrutement des mousses sur les navires, la traite de la fourrure, la coupe du bois et possiblement aussi l’esclavage pourraient expliquer cette « jeune » migration. Sur le plan alimentaire, les végétaux de type C3, la viande nourrie aux ressources C3 et le poisson faisaient partie du menu montréalais. Les plantes C4 (majoritairement maïs mais aussi sucre de canne [rhum]) étaient consommées en quantité variable. La question de l’influence de la migration sur l’alimentation n’a pu être explorée en profondeur en raison de contraintes liées à la contamination du d18O du carbonate des os. La combinaison des données ostéologiques et isotopiques à la distribution spatiale des sépultures, a permis d’étudier un aspect de l’archéologie funéraire à l’échelle individuelle (identité possible), sans toutefois fournir de résultats probants, à l’échelle du cimetière et de son organisation globale.

Organisation moléculaire dirigée par le groupe CONH2 en 2D et 3D

Notre étude a pour objet la conception, la synthèse ainsi que l’étude structurale d’architectures supramoléculaires obtenues par auto-assemblage, en se basant sur les concepts de la tectonique moléculaire. Cette branche de la chimie supramoléculaire s’occupe de la conception et la synthèse de molécules organiques appelées tectons, du grec tectos qui signifie constructeur. Le tecton est souvent constitué de sites de reconnaissance branchés sur un squelette bien choisi. Les sites de reconnaissance orientés par la géométrie du squelette peuvent participer dans des interactions intermoléculaires qui sont suffisamment fortes et directionnelles pour guider la topologie du cristal résultant. La stratégie envisagée utilise des processus d'auto-assemblage engageant des interactions réversibles entre les tectons. L’auto-assemblage dirigé par de fortes interactions intermoléculaires directionnelles est largement utilisé pour fabriquer des matériaux dont les composants doivent être positionnés en trois dimensions (3D) d'une manière prévisible. Cette stratégie peut également être utilisée pour contrôler l’association moléculaire en deux dimensions (2D), ce qui permet la construction de monocouches organisées et prédéterminées sur différents types des surfaces, tels que le graphite.Notre travail a mis l’accent sur le comportement de la fonction amide comme fonction de reconnaissance qui est un analogue du groupement carboxyle déjà utilisé dans plusieurs études précédentes. Nous avons étudié le comportement d’une série de composés contenant un noyau plat conçu pour faciliter l'adsorption sur le graphite et modifiés par l'ajout de groupes amide pour favoriser la formation de liaisons hydrogène entre les molécules ainsi adsorbées. La capacité de ces composés à former de monocouches organisées à l’échelle moléculaire en 2D a été examinée par microscopie à effet tunnel, etleur organisation en 3D a également été étudiée par cristallographie aux rayons X. Dans notre étude, nous avons systématiquement modifié la géométrie moléculaire et d'autres paramètres afin d'examiner leurs effets sur l'organisation moléculaire. Nos résultats suggèrent que les analyses structurales combinées en 2D et 3D constituent un important atout dans l'effort pour comprendre les interactions entre les molécules adsorbées et l’effet de l’interaction avec la surface du substrat.

Una secuencia didáctica para un concepto unificador en un curso de álgebra lineal de un programa de formación a la ingeniería

L’introduction aux concepts unificateurs dans l’enseignement des mathématiques privilégie typiquement l’approche axiomatique. Il n’est pas surprenant de constater qu’une telle approche tend à une algorithmisation des tâches pour augmenter l’efficacité de leur résolution et favoriser la transparence du nouveau concept enseigné (Chevallard, 1991). Cette réponse classique fait néanmoins oublier le rôle unificateur du concept et n’encourage pas à l’utilisation de sa puissance. Afin d’améliorer l’apprentissage d’un concept unificateur, ce travail de thèse étudie la pertinence d’une séquence didactique dans la formation d’ingénieurs centrée sur un concept unificateur de l’algèbre linéaire: la transformation linéaire (TL). La notion d’unification et la question du sens de la linéarité sont abordées à travers l’acquisition de compétences en résolution de problèmes. La séquence des problèmes à résoudre a pour objet le processus de construction d’un concept abstrait (la TL) sur un domaine déjà mathématisé, avec l’intention de dégager l’aspect unificateur de la notion formelle (Astolfi y Drouin, 1992). À partir de résultats de travaux en didactique des sciences et des mathématiques (Dupin 1995; Sfard 1991), nous élaborons des situations didactiques sur la base d’éléments de modélisation, en cherchant à articuler deux façons de concevoir l’objet (« procédurale » et « structurale ») de façon à trouver une stratégie de résolution plus sûre, plus économique et réutilisable. En particulier, nous avons cherché à situer la notion dans différents domaines mathématiques où elle est applicable : arithmétique, géométrique, algébrique et analytique. La séquence vise à développer des liens entre différents cadres mathématiques, et entre différentes représentations de la TL dans les différents registres mathématiques, en s’inspirant notamment dans cette démarche du développement historique de la notion. De plus, la séquence didactique vise à maintenir un équilibre entre le côté applicable des tâches à la pratique professionnelle visée, et le côté théorique propice à la structuration des concepts. L’étude a été conduite avec des étudiants chiliens en formation au génie, dans le premier cours d’algèbre linéaire. Nous avons mené une analyse a priori détaillée afin de renforcer la robustesse de la séquence et de préparer à l’analyse des données. Par l’analyse des réponses au questionnaire d’entrée, des productions des équipes et des commentaires reçus en entrevus, nous avons pu identifier les compétences mathématiques et les niveaux d’explicitation (Caron, 2004) mis à contribution dans l’utilisation de la TL. Les résultats obtenus montrent l’émergence du rôle unificateur de la TL, même chez ceux dont les habitudes en résolution de problèmes mathématiques sont marquées par une orientation procédurale, tant dans l’apprentissage que dans l’enseignement. La séquence didactique a montré son efficacité pour la construction progressive chez les étudiants de la notion de transformation linéaire (TL), avec le sens et les propriétés qui lui sont propres : la TL apparaît ainsi comme un moyen économique de résoudre des problèmes extérieurs à l’algèbre linéaire, ce qui permet aux étudiants d’en abstraire les propriétés sous-jacentes. Par ailleurs, nous avons pu observer que certains concepts enseignés auparavant peuvent agir comme obstacles à l’unification visée. Cela peut ramener les étudiants à leur point de départ, et le rôle de la TL se résume dans ces conditions à révéler des connaissances partielles, plutôt qu’à guider la résolution.

Étude de la formation et de l'évolution de nanostructures par méthodes Monte Carlo

Cette thèse, composée de quatre articles scientifiques, porte sur les méthodes numériques atomistiques et leur application à des systèmes semi-conducteurs nanostructurés. Nous introduisons les méthodes accélérées conçues pour traiter les événements activés, faisant un survol des développements du domaine. Suit notre premier article, qui traite en détail de la technique d'activation-relaxation cinétique (ART-cinétique), un algorithme Monte Carlo cinétique hors-réseau autodidacte basé sur la technique de l'activation-relaxation nouveau (ARTn), dont le développement ouvre la voie au traitement exact des interactions élastiques tout en permettant la simulation de matériaux sur des plages de temps pouvant atteindre la seconde. Ce développement algorithmique, combiné à des données expérimentales récentes, ouvre la voie au second article. On y explique le relâchement de chaleur par le silicium cristallin suite à son implantation ionique avec des ions de Si à 3 keV. Grâce à nos simulations par ART-cinétique et l'analyse de données obtenues par nanocalorimétrie, nous montrons que la relaxation est décrite par un nouveau modèle en deux temps: "réinitialiser et relaxer" ("Replenish-and-Relax"). Ce modèle, assez général, peut potentiellement expliquer la relaxation dans d'autres matériaux désordonnés. Par la suite, nous poussons l'analyse plus loin. Le troisième article offre une analyse poussée des mécanismes atomistiques responsables de la relaxation lors du recuit. Nous montrons que les interactions élastiques entre des défauts ponctuels et des petits complexes de défauts contrôlent la relaxation, en net contraste avec la littérature qui postule que des "poches amorphes" jouent ce rôle. Nous étudions aussi certains sous-aspects de la croissance de boîtes quantiques de Ge sur Si (001). En effet, après une courte mise en contexte et une introduction méthodologique supplémentaire, le quatrième article décrit la structure de la couche de mouillage lors du dépôt de Ge sur Si (001) à l'aide d'une implémentation QM/MM du code BigDFT-ART. Nous caractérisons la structure de la reconstruction 2xN de la surface et abaissons le seuil de la température nécessaire pour la diffusion du Ge en sous-couche prédit théoriquement par plus de 100 K.

Essai de détection de processus migratoires à travers les isotopes de strontium et d’oxygène : étude des restes humains du cimetière Saint-Matthew (Québec, 1771-1860)

Afin de distinguer les immigrants de première génération des individus nés à Québec et de discuter de l’identité des immigrants de cette ville aux XVIIIe et XIXe siècles, trente-quatre squelettes humains exhumés du cimetière protestant Saint-Matthew (Québec, 1771-1860) ont fait l’objet d’analyses ostéologiques et isotopiques du strontium (87Sr/86Sr) et de l’oxygène (δ18O). Les teneurs obtenues, bien que moins précises que les données historiques, ont permis de distinguer trois groupes d’origine, soit les individus nés à Québec (N = 12), les immigrants de première génération provenant le plus probablement des îles Britanniques et du nord de la France (N = 19) et les immigrants de première génération dont l’origine ne peut être précisée (N = 3). De plus, l’origine écossaise de certains individus a pu être suggérée en fonction de compositions isotopiques variant entre -10,0 et -9,09 % vs VSMOW. La comparaison des groupes d’origine à des données provenant de sources historiques et d’une étude antérieure a permis de dresser un portrait de l’identité des immigrants, à la fois sur les plans populationnel et individuel. De plus, les compositions isotopiques (δ18O, 87Sr/86Sr, δ13C et δ15N) nous laissent croire qu’au moins un individu pourrait être d’origine amérindienne et qu’un autre proviendrait d’une partie de l’Europe plus appauvrie en 18O (possiblement un pays scandinave ou une région alpine). La distribution spatiale des sépultures nous a également permis d’émettre des hypothèses sur les liens familiaux et sociaux d’immigrants inhumés en caveaux ou entassés de façon particulièrement modeste.

Solution Methods for Service Network Design with Resource Management Consideration

La gestion des ressources, équipements, équipes de travail, et autres, devrait être prise en compte lors de la conception de tout plan réalisable pour le problème de conception de réseaux de services. Cependant, les travaux de recherche portant sur la gestion des ressources et la conception de réseaux de services restent limités. La présente thèse a pour objectif de combler cette lacune en faisant l’examen de problèmes de conception de réseaux de services prenant en compte la gestion des ressources. Pour ce faire, cette thèse se décline en trois études portant sur la conception de réseaux. La première étude considère le problème de capacitated multi-commodity fixed cost network design with design-balance constraints(DBCMND). La structure multi-produits avec capacité sur les arcs du DBCMND, de même que ses contraintes design-balance, font qu’il apparaît comme sous-problème dans de nombreux problèmes reliés à la conception de réseaux de services, d’où l’intérêt d’étudier le DBCMND dans le contexte de cette thèse. Nous proposons une nouvelle approche pour résoudre ce problème combinant la recherche tabou, la recomposition de chemin, et une procédure d’intensification de la recherche dans une région particulière de l’espace de solutions. Dans un premier temps la recherche tabou identifie de bonnes solutions réalisables. Ensuite la recomposition de chemin est utilisée pour augmenter le nombre de solutions réalisables. Les solutions trouvées par ces deux méta-heuristiques permettent d’identifier un sous-ensemble d’arcs qui ont de bonnes chances d’avoir un statut ouvert ou fermé dans une solution optimale. Le statut de ces arcs est alors fixé selon la valeur qui prédomine dans les solutions trouvées préalablement. Enfin, nous utilisons la puissance d’un solveur de programmation mixte en nombres entiers pour intensifier la recherche sur le problème restreint par le statut fixé ouvert/fermé de certains arcs. Les tests montrent que cette approche est capable de trouver de bonnes solutions aux problèmes de grandes tailles dans des temps raisonnables. Cette recherche est publiée dans la revue scientifique Journal of heuristics. La deuxième étude introduit la gestion des ressources au niveau de la conception de réseaux de services en prenant en compte explicitement le nombre fini de véhicules utilisés à chaque terminal pour le transport de produits. Une approche de solution faisant appel au slope-scaling, la génération de colonnes et des heuristiques basées sur une formulation en cycles est ainsi proposée. La génération de colonnes résout une relaxation linéaire du problème de conception de réseaux, générant des colonnes qui sont ensuite utilisées par le slope-scaling. Le slope-scaling résout une approximation linéaire du problème de conception de réseaux, d’où l’utilisation d’une heuristique pour convertir les solutions obtenues par le slope-scaling en solutions réalisables pour le problème original. L’algorithme se termine avec une procédure de perturbation qui améliore les solutions réalisables. Les tests montrent que l’algorithme proposé est capable de trouver de bonnes solutions au problème de conception de réseaux de services avec un nombre fixe des ressources à chaque terminal. Les résultats de cette recherche seront publiés dans la revue scientifique Transportation Science. La troisième étude élargie nos considérations sur la gestion des ressources en prenant en compte l’achat ou la location de nouvelles ressources de même que le repositionnement de ressources existantes. Nous faisons les hypothèses suivantes: une unité de ressource est nécessaire pour faire fonctionner un service, chaque ressource doit retourner à son terminal d’origine, il existe un nombre fixe de ressources à chaque terminal, et la longueur du circuit des ressources est limitée. Nous considérons les alternatives suivantes dans la gestion des ressources: 1) repositionnement de ressources entre les terminaux pour tenir compte des changements de la demande, 2) achat et/ou location de nouvelles ressources et leur distribution à différents terminaux, 3) externalisation de certains services. Nous présentons une formulation intégrée combinant les décisions reliées à la gestion des ressources avec les décisions reliées à la conception des réseaux de services. Nous présentons également une méthode de résolution matheuristique combinant le slope-scaling et la génération de colonnes. Nous discutons des performances de cette méthode de résolution, et nous faisons une analyse de l’impact de différentes décisions de gestion des ressources dans le contexte de la conception de réseaux de services. Cette étude sera présentée au XII International Symposium On Locational Decision, en conjonction avec XXI Meeting of EURO Working Group on Locational Analysis, Naples/Capri (Italy), 2014. En résumé, trois études différentes sont considérées dans la présente thèse. La première porte sur une nouvelle méthode de solution pour le "capacitated multi-commodity fixed cost network design with design-balance constraints". Nous y proposons une matheuristique comprenant la recherche tabou, la recomposition de chemin, et l’optimisation exacte. Dans la deuxième étude, nous présentons un nouveau modèle de conception de réseaux de services prenant en compte un nombre fini de ressources à chaque terminal. Nous y proposons une matheuristique avancée basée sur la formulation en cycles comprenant le slope-scaling, la génération de colonnes, des heuristiques et l’optimisation exacte. Enfin, nous étudions l’allocation des ressources dans la conception de réseaux de services en introduisant des formulations qui modèlent le repositionnement, l’acquisition et la location de ressources, et l’externalisation de certains services. À cet égard, un cadre de solution slope-scaling développé à partir d’une formulation en cycles est proposé. Ce dernier comporte la génération de colonnes et une heuristique. Les méthodes proposées dans ces trois études ont montré leur capacité à trouver de bonnes solutions.

Practical and Foundational Aspects of Secure Computation

Il y a des problemes qui semblent impossible a resoudre sans l'utilisation d'un tiers parti honnete. Comment est-ce que deux millionnaires peuvent savoir qui est le plus riche sans dire a l'autre la valeur de ses biens ? Que peut-on faire pour prevenir les collisions de satellites quand les trajectoires sont secretes ? Comment est-ce que les chercheurs peuvent apprendre les liens entre des medicaments et des maladies sans compromettre les droits prives du patient ? Comment est-ce qu'une organisation peut ecmpecher le gouvernement d'abuser de l'information dont il dispose en sachant que l'organisation doit n'avoir aucun acces a cette information ? Le Calcul multiparti, une branche de la cryptographie, etudie comment creer des protocoles pour realiser de telles taches sans l'utilisation d'un tiers parti honnete. Les protocoles doivent etre prives, corrects, efficaces et robustes. Un protocole est prive si un adversaire n'apprend rien de plus que ce que lui donnerait un tiers parti honnete. Un protocole est correct si un joueur honnete recoit ce que lui donnerait un tiers parti honnete. Un protocole devrait bien sur etre efficace. Etre robuste correspond au fait qu'un protocole marche meme si un petit ensemble des joueurs triche. On demontre que sous l'hypothese d'un canal de diusion simultane on peut echanger la robustesse pour la validite et le fait d'etre prive contre certains ensembles d'adversaires. Le calcul multiparti a quatre outils de base : le transfert inconscient, la mise en gage, le partage de secret et le brouillage de circuit. Les protocoles du calcul multiparti peuvent etre construits avec uniquements ces outils. On peut aussi construire les protocoles a partir d'hypoth eses calculatoires. Les protocoles construits a partir de ces outils sont souples et peuvent resister aux changements technologiques et a des ameliorations algorithmiques. Nous nous demandons si l'efficacite necessite des hypotheses de calcul. Nous demontrons que ce n'est pas le cas en construisant des protocoles efficaces a partir de ces outils de base. Cette these est constitue de quatre articles rediges en collaboration avec d'autres chercheurs. Ceci constitue la partie mature de ma recherche et sont mes contributions principales au cours de cette periode de temps. Dans le premier ouvrage presente dans cette these, nous etudions la capacite de mise en gage des canaux bruites. Nous demontrons tout d'abord une limite inferieure stricte qui implique que contrairement au transfert inconscient, il n'existe aucun protocole de taux constant pour les mises en gage de bit. Nous demontrons ensuite que, en limitant la facon dont les engagements peuvent etre ouverts, nous pouvons faire mieux et meme un taux constant dans certains cas. Ceci est fait en exploitant la notion de cover-free families . Dans le second article, nous demontrons que pour certains problemes, il existe un echange entre robustesse, la validite et le prive. Il s'effectue en utilisant le partage de secret veriable, une preuve a divulgation nulle, le concept de fantomes et une technique que nous appelons les balles et les bacs. Dans notre troisieme contribution, nous demontrons qu'un grand nombre de protocoles dans la litterature basee sur des hypotheses de calcul peuvent etre instancies a partir d'une primitive appelee Transfert Inconscient Veriable, via le concept de Transfert Inconscient Generalise. Le protocole utilise le partage de secret comme outils de base. Dans la derniere publication, nous counstruisons un protocole efficace avec un nombre constant de rondes pour le calcul a deux parties. L'efficacite du protocole derive du fait qu'on remplace le coeur d'un protocole standard par une primitive qui fonctionne plus ou moins bien mais qui est tres peu couteux. On protege le protocole contre les defauts en utilisant le concept de privacy amplication .