Massively multiplayer online games (MMOG) have become an extremely popular genre of gaming boasting millions of subscribers. Focusing on cheating, game designers often implement client-server network models which ensure that authority over the gamestate is retained by the game providers. Due to scalability limitations of such architecture the transition to the more scalable, yet less secure, peer to peer (P2P) models has become a more attractive option. Concentrating on cheat detection, the IRS hybrid network model is proposed. It combines positive features from both network designs and represents a reasonable trade-off between security and network efficiency. The IRS model's centralized server acts as the authority over the game-state, managing peer to peer matching and monitoring client behaviour. This allows for a reduced computational load by enabling clients to resolve messages for others. Intermittent peer auditing which compares two client's computation of the same request message also allows for the discovery and elimination of cheating behaviour. By simulating the proposed hybrid model in an abstract game environment designed to incorporate parameters of actual gameplay it is shown that malicious clients are purged extremely quickly and with minimal impact on non-cheating clients, while still ensuring continued benefit and scalability from distributed computation. Since cheating has a very serious impact on gaming it is essential that any study into the improvement of MMOG network models strives to preserve security. / Les jeux en ligne massivement multi-joueur (MMOG) sont un genre de jeu devenu extrêmement populaire, avec des millions d'abonnés. Pour éviter les situations de tricherie, les concepteurs de jeux favorisent le modèle réseau client/serveur (C/S) parce qu'il garantie que l'autorité sur l'état du jeu est conservée par le fournisseur du jeu. Cependant, l'évolution de tel modèle est limité. Malgré leur lacune au niveau de la sécurité, les modèles pair-à-pair (P2P) sont une alternative intéressante. Nous proposons un modèle de réseau hybride, l'IRS, qui se spécialise dans la détection des cas de tricherie. Ce modèle exploite les aspects positifs des deux types de modèle réseau (C/S et P2P), tout en proposant un compromis raisonnable entre la sécurité et l'efficacité. Dans le modèle IRS, un serveur centralisé possède l'autorité absolue sur l'état du jeu, tout en assurant la gestion des communications pair-à-pair et la surveillance du comportement des participants. En permettant aux participants d'exécuter des messages pour d'autres participants, la charge d'exécution sur le serveur est réduite. Les cas de tricherie peuvent être découverts et éliminés à l'aide d'audits intermittentes qui comparent les résultats d'exécution d'un même message par deux participants. Des simulations du modèle hybride proposé ont été effectuées dans un environnement jeu visant à reproduire des situations de jeux réelles. Les résultats démontrent le modèle expulse les participants malveillants très rapidement du jeu avec des impacts minimaux aux autres participants, tout en conservant les avantages d'extensibilité des modèles distribués. Puisq

This thesis proposes a new computational framework for the modeling of biological tissue structure in diffusion MRI data. By measuring the local Brownian motion of water molecules, diffusion MRI provides estimates of local fibre orientations in tissues such as the white matter of the brain. Over the last years, diffusion MRI has become an important tool for the in vivo study of brain connectivity. Nevertheless, the inference of the structure of white matter fibres is still an open problem. The methodology introduced in this thesis is based on differential geometry and perceptual organisation. The key ideas are to model white matter fibres as 3D space curves, to view diffusion MRI data as providing information about the tangent vectors of these curves, and to frame the problem as that of inferring 3D curve geometry from a discretized, incomplete, and potentially blurred and noisy field of tangent measurements. Inspired by notions used in perceptual organisation in computer vision, we develop local geometric constraints which guide the inference process and ultimately result in the recovery of the underlying fibre geometry. We start by introducing a notion of co-helicity between triplets of orientation estimates, which is incorporated in a geometric inference process. This process is referred to as 3D curve inference, and it estimates the parameters of the local best-fit osculating helix for each orientation in the dataset. Based on this, a relaxation labeling framework is set-up for the regularization of diffusion MRI data. We then develop a 3D curve inference technique for the identification of complex sub-voxel fibre configurations in high angular resolution diffusion / Cette thèse présente une méthodologie pour la modélisation de la structure de tissus biologiques à partir de données d'imagerie par résonance magnetique (IRM) de diffusion. En mesurant le mouvement Brownien des molécules d'eau, l'IRM de diffusion permet d'estimer localement les orientations des fibres de matière blanche dans le cerveau. L'IRM de diffusion est un outil important pour l'étude in vivo de la connectivité du cerveau. Cependant, l'inférence de la structure des fibres de matière blanche demeure un problème en grande partie irrésolu. La méthodologie présentée dans cette thèse est basée sur la géométrie différentielle ainsi que sur l'organisation perceptuelle. Étant donné que les fibres de matière blanche peuvent être représentées par des courbes en 3D, et que l'IRM de diffusion donne des mesures reliées aux vecteurs tangents de ces courbes, le problème de base consiste à faire l'inférence de la géométrie de courbes en 3D, à partir de mesures de vecteurs tangents qui sont discretisées, incomplètes, et qui peuvent aussi être floues et bruitées. En se basant sur des notions empruntées à l'organisation perceptuelle en vision par ordinateur, nous développons des contraintes géométriques locales qui guident le processus d'inférence et dont le résultat ultime est la reconstruction de la géométrie des fibres sous-jacentes. Nous débutons par l'introduction d'une notion de co-hélicité entre des triplets d'estimés d'orientation, qui est incorporée dans un processus d'inférence géométrique. Cette méthode est appelée "3D curve inference" (inférence de courbes en 3D), et elle estime les paramètres de l'hélice osculatrice

MATLAB is a popular dynamic array-based language commonly used by students, scientists and engineers who appreciate the interactive development style, the rich set of array operators, the extensive builtin library, and the fact that they do not have to declare static types. Even though these users like to program in MATLAB, their computations are often very compute-intensive and are better suited for emerging high performance computing systems. This thesis reports on MIX10, a source-to-source compiler that automatically translates MATLAB programs to X10, a language designed for "Performance and Productivity at Scale"; thus, helping scientific programmers make better use of high performance computing systems.There is a large semantic gap between the array-based dynamically-typed nature of MATLAB and the object-oriented, statically-typed, and high-level array abstractions of X10. This thesis addresses the major challenges that must be overcome to produce sequential X10 code that is competitive with state-of-the-art static compilers for MATLAB which target more conventional imperative languages such as C and Fortran. Given that efficient basis, the thesis then provides a translation for the MATLAB parfor construct that leverages the powerful concurrency constructs in X10.The MIX10 compiler has been implemented using the McLab compiler tools, is open source, and is available both for compiler researchers and end-user MATLAB programmers. We have used the implementation to perform many empirical measurements on a set of 17 MATLAB benchmarks. We show that our best MIX10-generated code is significantly faster than the de facto Mathworks' MATLAB system, and that our results are competitive with state-of-the-art static compilers that target C and Fortran. We also show the importance of finding the correct approach to representing the arrays in X10, and the necessity of an IntegerOkay analysis that determines which double variables can be safely represented as integers. Finally, we show that our X10-based handling of the MATLAB parfor greatly outperforms the de facto MATLAB implementation. / MATLAB est un langage de programmation dynamique, orienté-tableaux communément utilisé par les étudiants, les scientifiques et les ingénieurs qui apprécient son style de développement interactif, la richesse de ses opérateurs sur les tableaux, sa librairie impressionnante de fonctions de base et le fait qu'on aie pas à déclarer statiquement le type des variables. Bien que ces usagers apprécient MATLAB, leurs programmes nécessitent sou- vent des ressources de calcul importantes qui sont offertes par les nouveaux systèmes de haute performance. Cette thèse fait le rapport de MIX10, un compilateur source-à-source qui fait la traduction automatique de programmes MATLAB à X10, un langage construit pour "la performance et la productivité à grande échelle." Ainsi, MIX10 aide les program- meurs scientifiques à faire un meilleur usage des ressources des systèmes de calcul de haute performance.Il y a un écart sémantique important entre le typage dynamique et le focus sur les tableaux de MATLAB et l'approche orientée-objet, le typage statique et les abstractions de haut niveau sur les tableaux de X10. Cette thèse discute des défis principaux qui doivent être surmontés afin de produire du code X10 séquentiel compétitif avec les meilleurs compilateurs statiques pour MATLAB qui traduisent vers des langages impératifs plus conventionnels, tels que C et Fortran. Fort de cette fondation efficace, cette thèse décrit ensuite la traduction de l'instruction parfor de MATLAB afin d'utiliser les opérations sophistiquées de traitement concurrent de X10.Le compilateur MIX10 a été implémenté à l'aide de la suite d'outils de McLab, un projet libre de droits, disponible à la communauté de recherche ainsi qu'aux utilisateurs de MATLAB. Nous avons utilisé notre implémentation afin d'effectuer des mesures empiriques de performance sur un jeu de 17 programmes MATLAB. Nous démontrons que le code généré par MIX10 est considérablement plus rapide que le système MATLAB de Mathworks et que nos résultats sont compétitifs avec les meilleurs compilateurs statiques qui produisent du code C et Fortran. Nous montrons également l'importance d'une représentation appropriée des tableaux en X10 et la nécessité d'une analyse IntegerOkay qui permet de déter- miner quelles variables de type réel (double) peuvent être correctement représentées par des entiers (int). Finalement, nous montrons que notre traitement de l'instruction parfor en X10 nous permet d'atteindre des vitesses d'exécution considérablement meilleures que dans MATLAB.

Most traditional database systems offer secondary indexing to increase the performance of data reads during query execution. With the advent of newer, NoSQL distributed datastores, some don't yet have a secondary indexing feature built in. HBase is one such distributed database system. It partitions tables in so-called table regions across many nodes but does not offer secondary indexing. Since some types of queries may benefit from secondary indexing in order to improve their performance, we endeavoured to implement such secondary indexing for HBase. In this thesis, we present and compare two coprocessor based secondary indexing implementations.The first implementation, Table Based Secondary Indexing, leverages HBase tables to store the secondary indices. Query processing in our first implementation is split between the client and the servers.Our second implementation, In Memory Secondary Indexing, relies on indices that are partitioned and are co-located in the main memory of the table regions they index. Query processing in our second implementation is executed solely at the server level.Our experimental results show that both our implementations offer a substantial gain in read performance over the default HBase method of executing queries, which scans all table regions when executing read queries. / La majorité des systèmes de bases de données traditionnels ont un mécanisme d'indexation secondaire qui offre une performance accrue lors de requêtes en lecture. Du au développement récent des systèmes de base de données distribués, certains n'ont pas encore de mécanisme d'indexation secondaire. HBase est un de ces systèmes qui n'offre pas d'index secondaires. Dû au fait que la performance de certains types de requêtes peuvent bénéficier grandement des index secondaires, nous nous sommes engagés à créer ce mécanisme pour HBase. Dans cette thèse, nous faisons la présentation et la comparaison de deux solutions que nous avons créées qui basées sur l'utilisation des coprocesseurs de HBase.La première solution repose sur l'utilisation des tables offertes par HBase pour emmagasiner les index secondaires. Dans notre première solution, l'exécution de requêtes utilisant un index secondaire est partagée entre le client et le serveur.La seconde solution se base sur le fait que les index secondaire sont partitionnés pour correspondre aux régions de tables et sont co-localisées avec celles-ci. De plus, les index secondaires résident dans la mémoire active des serveurs. Dans notre deuxième solution, l'exécution de requêtes utilisant un index secondaire est faite uniquement par les serveurs.Nos résultats expérimentaux montrent que nos deux solutions offrent un gain de performance substantiel lors d'exécutions de requêtes en lecture comparé à la méthode native à HBase.

In this thesis we investigate the mappability of human genome and we look at some reasons that might cause unmappability in a region. We look at transposable elements and genome duplications as the main reasons for unmappability. In this analysis we simulated singled end, paired end and mate paired reads of 6 different lengths and we used BWA to map these simulated reads to the human genome. We assumed that a position in the genome is mappable if there is at least one unique read mapped to that position. We looked at unmappable regions and fraction of transposable elements or genome duplications corresponding to these regions. We also looked at age distribution of transposable elements and genome duplications that are in unmappable regions. Our results shows that regions that are in younger and longer transposable elements are harder to sequence. In order to compare our simulated data with a real sequencing data, we used the output of a sequencing from Illumina to compare coverage of genome in this real data set with our mappability results. We show that 4.1% of genome that is mappable in our simulations result, has low coverage in real sequencing data. We also investigated the reasons behind having low coverage in mappable regions. Our simulation result shows the impact of transposable elements and other repeats on mappability in the human genome and we show that using longer paired end and mate paired reads improves the mappability of the human genome. / Dans cette thèse, nous étudions la "visibilité" du génome humain par des méthodes séquençage modernes et nous regardons quelles sont les raisons qui pourraient causer l'absence de visibilité dans une région donnée. Nous montrons que les éléments transposables et les duplications de génome sont les principaux obstables à la visibilité de régions génomiques. Dans cette analyse, nous avons utilisé des reads simulés, de types individuels ou pairés, de 6 longueurs différentes et nous avons utilisé BWA pour assigner ces reads au génome humain. Nous avons supposé que la position dans le génome est visible s'il y a au moins un read unique assigné à cette position. Nous avons examiné les régions non visibles et la fraction d'éléments transposables ou des duplications de génome correspondant à ces régions. Nous avons également examiné la distribution d'âge des éléments transposables et des duplications de génome qui sont dans les régions non visibles. Nos résultats montrent que les régions qui sont des éléments plus jeunes et plus transposable sont plus difficiles à séquencer. Afin de comparer nos données simulées avec les données réelles de séquençage, nous avons utilisé des données de reséquençage provenant d'un séquençage Illumina pour comparer la couverture observée du génome avec nos résultats provenant de données simulées. Nous montrons que 4,1% du génome qui est visible dans nos simulations a une faible couverture dans les données de séquençage réelles. Nous avons également étudié les raisons pouvant expliquer une faible couverture dans les régions visibles. Les résultats de nos simulations montrent l'impact des éléments transposables et les autres répétitions sur la visibilité dans le génome humain et nous montrent que l'utilisation de long reads pairés améliorent la visibilité du génome humain.

MATLAB is a dynamic numerical scripting language widely used by scientists, engineers and students. While MATLAB's high-level syntax and dynamic types make it ideal for fast prototyping, programmers often prefer using high-performance static languages such as FORTRAN for their final distribution. Rather than rewriting the code by hand, our solution is to provide a source-to-source compiler that translates the original MATLAB program to an equivalent FORTRAN program.In this thesis, we introduce MC2FOR, a source-to-source compiler which transforms MATLAB to FORTRAN and handles several important challenges during the transformation, such as efficiently estimating the static type characteristics of all the variables in a given MATLAB program, mapping numerous MATLAB built-in functions to FORTRAN, and correctly supporting some MATLAB dynamic features in the generated FORTRAN code.This compiler consists of two major parts. The first part is an interprocedural analysis component to estimate the static type characteristics, such as the shapes of the arrays and the ranges of the scalars, which are used to generate variable declarations and to remove unnecessary array bounds checking in the translated FORTRAN program. The second part is an extensible FORTRAN code generation framework automatically transforming MATLAB constructs to equivalent FORTRAN constructs.This work has been implemented within the McLab framework, and we evaluated the performance of the MC2FOR compiler on a collection of 20 MATLAB benchmarks. For most of the benchmarks, the generated FORTRAN program runs 1.2 to 337 times faster than the original MATLAB program, and in terms of physical lines of code, typically grows only by a factor of around 2. These experimental results show that the code generated by MC2FOR performs better on average, at the cost of only a modest increase in code size. / MATLAB est un langage de script dynamique très utilisé par les scientifiques, les ingénieurs et les étudiants. La syntaxe de haut niveau et le typage dynamique de MATLAB en font un langage idéal pour faire du prototypage rapide, mais les programmeurs préfèrent souvent utiliser des langages statiques performants comme FORTRAN pour la distribution finale. Au lieu de réécrire le code à la main, notre solution est de proposer un compilateur qui traduit le programme MATLAB original vers un program FORTRAN équivalent.Dans cette thèse, nous introduisons MC2FOR, un compilateur qui transforme MATLAB vers FORTRAN et surmonte plusieurs difficultés importantes rencontrées durant la transformation, dont celles d'estimer efficacement le type statique de toutes les variables dans un programme MATLAB donné, de trouver une correspondance pour les nombreuses fonctions intégrées de MATLAB vers FORTRAN et de supporter correctement quelques caractéristiques dynamiques de MATLAB dans le code FORTRAN généré.Le compilateur est constitué de deux parties majeures: la première partie est une analyse interprocédurale qui estime des caractéristiques du type statique, comme la forme des tableaux et les limites des scalaires, qui sont utlilisées pour générer des déclarations de variables et pour supprimer les vérifications de limite de tableaux inutiles dans le programme FORTRAN généré. La deuxième partie est un framework de génération de code extensible qui transforment utomatiquement des constructions de MATLAB vers des constructions de FORTRAN équivalentes.Ce travail a été implementé dans le framework McLab, et nous avons évalué les performances du compilateur MC2FOR sur une collection de 20 programmes MATLAB. Pour la plupart des programmes, le programme FORTRAN généré s'éxécute entre 1.2 et 337 fois plus rapidement que le programme MATLAB original, et en termes de lignes de code, grandit seulement par un facteur de deux. Ces résultats expérimentaux démontrent que MC2FOR est en mesure de générer du code qui performe mieux en moyenne que l'original sans pour autant augmenter de trop sa taille.

This thesis identifies a formal connection between physical problems related to entanglement detection and complexity classes in theoretical computer science. In particular, we prove that to nearly every quantum interactive proof complexity class (including BQP, QMA, QMA(2), QSZK, and QIP), there corresponds a natural entanglement or correlation detection problem that is complete for that class. In this sense, we can say that an entanglement or correlation detection problem captures the expressive power of each quantum interactive proof complexity class, and the contrast between such problems gives intuition to the differences between classes of quantum interactive proofs. It is shown that the difficulty of entanglement detection also depends on whether the distance measure used is the trace distance or the one-way LOCC distance. We also provide analysis for another problem of this flavour, which we show is decidable by a two-message quantum interactive proof system while being hard for both NP and QSZK, the first nontrivial example of such a problem. / Ce mémoire met en évidence un lien formel entre les problèmes physiques de détection d'intrication et les classes de complexité de l'informatique théorique. Plus particulièrement, nous établissons une correspondance entre la plupart des classes de complexité naturelles issues de preuves interactives quantiques (incluant BQP, QMA, QMA(2), QSZK, et QIP), et une intrication ou un problème de détection de corrélation qui est complet pour cette classe. En ce sens, nous pouvons dire que l'intrication, ou le problème de détection de corrélation, capture la puissance expressive de chaque classe de complexité de preuve interactive quantique et que le contraste entre de tels problèmes donne une idée sur les différences entre les classes de preuves interactives quantiques. Il est démontré que la difficulté de la détection d'intrication varie considérablement du fait que la mesure de distance utilisée soit la distance de trace ou LOCC unidirectionnel. Nous fournissons également l'analyse d'un problème similaire, et montrons que celui-ci est décidable par un système de preuve interactive quantique (de deux messages) tout en étant NP-dur ainsi que QSZK-dur, le premier exemple non trivial d'un tel problème.

With the growing size of Application Programming Interfaces (APIs), both API usability and API learning become more challenging. API learning resources are often crucial for helping developers learn an API, but they are distributed across different documents, which makes finding the necessary information more challenging. This work focuses on discovering relevant sections of tutorials for a given API type. We approach this problem by identifying API types in an API tutorial, dividing the tutorial into small fragments and classifying them based on linguistic and structural features. The system we developed can ease information discovery for the developers who need information about a particular API type. Experiments conducted on five tutorials show that our approach is able to discover sections relevant to an API type with 0.79 average precision, 0.73 average recall, and 0.75 average F1 measure when trained and tested on the same tutorial. When trained on four tutorials and tested on a fifth tutorial the average precision is 0.84, average recall is 0.62, and the F1 measure is 0.71. / Avec la taille grandissante des interfaces de programmation (API), l'aptitude àl'utilisation ainsi que la facilité d'apprentissage deviennent des préoccupations de premier ordre. La disponibilité de ressources d'apprentissage des API est de grande importance pour parvenir à developer efficacement à partir de différentes sources de documentation. Ce mémoire est consacré au problème de découverte automatique de sections pertinentes contenues dans les tutoriels des API. Nous traitons ce problème en commençant par l'identification du type d'API d'un tutoriel pour ensuite le diviser en fragments qui seront classés d'après leurs propriétés structurelles et linguistiques. Le système que nous avons développé rend le processus de découverte de sections de tutoriel beaucoup plus facile. Une évaluation de notre système a été réalisée avec cinq tutoriels et montre que notre approche peut découvrir des sections pertinentes avec une précision moyenne de 0.79, 0.73 en moyenne de rappel, et 0.75 de mesure moyenne F1 lorsque entraîné ettesté pour le même tutoriel. Lorsqu'entraîné depuis quatre tutoriels et testé dans avec le cinquième, nous obtenons 0.84 de précision moyenne, 0.62 de moyenne de rappel, et finalement 0.71 de mesure F1

Communication complexity studies how many bits a certain number of parties need to communicate with each other in order to compute a function whose input is distributed among those parties. Although it is a natural area of investigation based on practical considerations, the main motivation comes from the myriad of applications in theoretical computer science.This thesis has three main parts, studying three different aspects of communication complexity.1. The first part is concerned with the k-party communication complexity of functions F:({0,1}^n)^k -> {0,1} in the 'number on the forehead' (NOF) model. This is a fundamental model with many applications. In this model we study composed functions f of g. These functions include most of the well-known and studied functions in communication complexity literature. A major goal is to understand which combinations of f and g lead to hard communication functions. In particular, due to important circuit applications, it is of great interest to understand how powerful the NOF model becomes when k is log n or more. Motivated by these goals, we show that there is an efficient O(log^3 n) cost simultaneous protocol for sym of g when k > 1+log n, sym is any symmetric function and g is any function. This class of functions includes some functions that were previously conjectured to be hard and our result rules this class out for possible very important circuit complexity applications. We also give Ramsey theoretic applications of our efficient protocol. In the setting of k < log n, we study more closely functions of the form majority of g, mod_m of g, and nor of g, where the latter two are generalizations of the well-known functions Inner Product and Disjointness respectively. We characterize the communication complexity of these functions with respect to the choice of g. As the main application, we answer a question posed by Babai et al. (SIAM Journal on Computing, 33:137--166, 2004) and determine the communication complexity of majority of qcsb, where qcsb is the "quadratic character of the sum of the bits" function. 2. The second part is about Fourier analysis of symmetric boolean functions and its applications in communication complexity and other areas. The spectral norm of a boolean function f:{0,1}^n -> {0,1} is the sum of the absolute values of its Fourier coefficients. This quantity provides useful upper and lower bounds on the complexity of a function in areas such as communication complexity, learning theory and circuit complexity. We give a combinatorial characterization for the spectral norm of symmetric functions. We show that the logarithm of the spectral norm is of the same order of magnitude as r(f)log(n/r(f)) where r(f) = max(r_0,r_1), and r_0 and r_1 are the smallest integers less than n/2 such that f(x) or f(x)parity(x) is constant for all x with x_1 + ... + x_n in [r_0, n-r_1]. We present some applications to the decision tree and communication complexity of symmetric functions. 3. The third part studies privacy in the context of communication complexity: how much information do the players reveal about their input when following a communication protocol? The unattainability of perfect privacy for many functions motivates the study of approximate privacy. Feigenbaum et al. (Proceedings of the 11th Conference on Electronic Commerce, 167--178, 2010) defined notions of worst-case as well as average-case approximate privacy, and presented several interesting upper bounds, and some open problems for further study. In this thesis, we obtain asymptotically tight bounds on the trade-offs between both the worst-case and average-case approximate privacy of protocols and their communication cost for Vickrey Auction, which is the canonical example of a truthful auction. We also prove exponential lower bounds on the approximate privacy of protocols computing the Intersection function, independent of its communication cost. This proves a conjecture of Feigenbaum et al. / La complexité de communication étudie combien de bits un groupe de joueurs donné doivent échanger entre eux pour calculer une function dont l'input est distribué parmi les joueurs. Bien que ce soit un domaine de recherche naturel basé sur des considérations pratiques, la motivation principale vient des nombreuses applications théoriques.Cette thèse comporte trois parties principales, étudiant trois aspects de la complexité de communication.1. La première partie discute le modèle 'number on the forehead' (NOF) dans la complexité de communication à plusieurs joueurs. Il s'agit d'un modèle fondamental en complexité de communication, avec des applications à la complexité des circuits, la complexité des preuves, les programmes de branchement et la théorie de Ramsey. Dans ce modèle, nous étudions les fonctions composeés f de g. Ces fonctions comprennent la plupart des fonctions bien connues qui sont étudiées dans la littérature de la complexité de communication. Un objectif majeur est de comprendre quelles combinaisons de f et g produisent des compositions qui sont difficiles du point de vue de la communication. En particulier, à cause de l'importance des applications aux circuits, il est intéressant de comprendre la puissance du modèle NOF quand le nombre de joueurs atteint ou dépasse log n. Motivé par ces objectifs nous montrons l'existence d'un protocole simultané efficace à k joueurs de coût O(log^3 n) pour sym de g lorsque k > 1 + log n, sym est une function symmétrique quelconque et g est une fonction arbitraire. Nous donnons aussi des applications de notre protocole efficace à la théorie de Ramsey.Dans le contexte où k < log n, nous étudions de plus près des fonctions de la forme majority de g, mod_m de g et nor de g, où les deux derniers cas sont des généralisations des fonctions bien connues et très étudiées Inner Product et Disjointness respectivement. Nous caractérisons la complexité de communication de ces fonctions par rapport au choix de g.2. La deuxième partie considère les applications de l'analyse de Fourier des fonctions symmétriques à la complexité de communication et autres domaines. La norme spectrale d'une function booléenne f:{0,1}^n -> {0,1} est la somme des valeurs absolues de ses coefficients de Fourier. Nous donnons une caractérisation combinatoire pour la norme spectrale des fonctions symmétriques. Nous montrons que le logarithme de la norme spectrale est du même ordre de grandeur que r(f)log(n/r(f)), avec r(f) = max(r_0,r_1) où r_0 et r_1 sont les entiers minimaux plus petits que n/2 pour lesquels f(x) ou f(x)parity(x) est constant pour tout x tel que x_1 + ... + x_n à [r_0,n-r_1]. Nous présentons quelques applications aux arbres de décision et à la complexité de communication des fonctions symmétriques.3. La troisième partie étudie la confidentialité dans le contexte de la complexité de communication: quelle quantité d'information est-ce que les joueurs révèlent sur leur input en suivant un protocole donné? L'inatteignabilité de la confidentialité parfaite pour plusieurs fonctions motivent l'étude de la confidentialité approximative. Feigenbaum et al. (Proceedings of the 11th Conference on Electronic Commerce, 167--178, 2010) ont défini des notions de confidentialité approximative dans le pire cas et dans le cas moyen, et ont présenté plusieurs bornes supérieures intéressantes ainsi que quelques questions ouvertes. Dans cette thèse, nous obtenons des bornes asymptotiques précises, pour le pire cas aussi bien que pour le cas moyen, sur l'échange entre la confidentialité approximative de protocoles et le coût de communication pour les enchères Vickrey Auction, qui constituent l'exemple canonique d'une enchère honnête. Nous démontrons aussi des bornes inférieures exponentielles sur la confidentialité approximative de protocoles calculant la function Intersection, indépendamment du coût de communication. Ceci résout une conjecture de Feigenbaum et al.

Protein-protein interactions represent a crucial source of information for the understanding of the biological mechanisms of the cell. In order to be useful, high quality protein-protein interactions must be computationally extracted from the noisy datasets produced by high-throughput experiments such as affinity purification. Even when filtered protein-protein interaction datasets are obtained, the task of analyzing the network formed by these numerous interactions remains tremendous. Protein-protein interaction networks are large, intricate, and require computational approaches to provide meaningful biological insights. The overall objective of this thesis is to explore algorithms assessing the quality of protein-protein interactions and facilitating the analysis of their networks. This work is divided into four results: 1) a novel Bayesian approach to model contaminants originating from affinity purifications, 2) a new method to identify and evaluate the quality of protein-protein interactions independently in different cell compartments, 3) an algorithm computing the statistical significance of clusterings of proteins sharing the same functional annotation in protein-protein interaction networks, and 4) a computational tool performing sequence motif discovery in 5' untranslated regions as well as evaluating the clustering of such motifs in protein-protein interaction networks. / Les interactions protéine-protéine représentent une source d'information essentielle à la compréhension des divers méchanismes biologiques de la cellule. Cependant, les expériences à haut débit qui identifient ces interactions, comme la purification par affinité, produisent un très grand nombre de faux-positifs. Des méthodes computationelles sont donc requises afin d'extraire de ces ensembles de données les interactions protéine-protéine de grande qualité. Toutefois, même lorsque filtrés, ces ensembles de données forment des réseaux très complexes à analyser. Ces réseaux d'interactions protéine-protéine sont d'une taille importante, d'une grande complexité et requièrent des approches computationelles sophistiquées afin d'en retirer des informations possédant une réelle portée biologique. L'objectif de cette thèse est d'explorer des algorithmes évaluant la qualité d'interactions protéine-protéine et de faciliter l'analyse des réseaux qu'elles composent. Ce travail de recherche est divisé en quatre principaux résultats: 1) une nouvelle approche bayésienne permettant la modélisation des contaminants provenant de la purification par affinité, 2) une nouvelle méthode servant à la découverte et l'évaluation de la qualité d'interactions protéine-protéine à l'intérieur de différents compartiments de la cellule, 3) un algorithme détectant les regroupements statistiquement significatifs de protéines partageant une même annotation fonctionnelle dans un réseau d'interactions protéine-protéine et 4) un outil computationel qui a pour but la découverte de motifs de séquences dans les régions 5' non traduites tout en évaluant le regroupement de ces motifs dans les réseaux d'interactions protéine-protéine.