Amplification de l'amplitude : analyse et applications

Ce mémoire étudie l'algorithme d'amplification de l'amplitude et ses applications dans le domaine de test de propriété. On utilise l'amplification de l'amplitude pour proposer le plus efficace algorithme quantique à ce jour qui teste la linéarité de fonctions booléennes et on généralise notre nouvel algorithme pour tester si une fonction entre deux groupes abéliens finis est un homomorphisme. Le meilleur algorithme quantique connu qui teste la symétrie de fonctions booléennes est aussi amélioré et l'on utilise ce nouvel algorithme pour tester la quasi-symétrie de fonctions booléennes. Par la suite, on approfondit l'étude du nombre de requêtes à la boîte noire que fait l'algorithme d'amplification de l'amplitude pour amplitude initiale inconnue. Une description rigoureuse de la variable aléatoire représentant ce nombre est présentée, suivie du résultat précédemment connue de la borne supérieure sur l'espérance. Suivent de nouveaux résultats sur la variance de cette variable. Il est notamment montré que, dans le cas général, la variance est infinie, mais nous montrons aussi que, pour un choix approprié de paramètres, elle devient bornée supérieurement.

Complexité raffinée du problème d'intersection d'automates

Le problème d'intersection d'automates consiste à vérifier si plusieurs automates finis déterministes acceptent un mot en commun. Celui-ci est connu PSPACE-complet (resp. NL-complet) lorsque le nombre d'automates n'est pas borné (resp. borné par une constante). Dans ce mémoire, nous étudions la complexité du problème d'intersection d'automates pour plusieurs types de langages et d'automates tels les langages unaires, les automates à groupe (abélien), les langages commutatifs et les langages finis. Nous considérons plus particulièrement le cas où chacun des automates possède au plus un ou deux états finaux. Ces restrictions permettent d'établir des liens avec certains problèmes algébriques et d'obtenir une classification intéressante de problèmes d'intersection d'automates à l'intérieur de la classe P. Nous terminons notre étude en considérant brièvement le cas où le nombre d'automates est fixé.

On some Density Theorems in Number Theory and Group Theory

Gowers, dans son article sur les matrices quasi-aléatoires, étudie la question, posée par Babai et Sos, de l'existence d'une constante $c>0$ telle que tout groupe fini possède un sous-ensemble sans produit de taille supérieure ou égale a $c|G|$. En prouvant que, pour tout nombre premier $p$ assez grand, le groupe $PSL_2(\mathbb{F}_p)$ (d'ordre noté $n$) ne posséde aucun sous-ensemble sans produit de taille $c n^{8/9}$, il y répond par la négative. Nous allons considérer le probléme dans le cas des groupes compacts finis, et plus particuliérement des groupes profinis $SL_k(\mathbb{Z}_p)$ et $Sp_{2k}(\mathbb{Z}_p)$. La premiére partie de cette thése est dédiée à l'obtention de bornes inférieures et supérieures exponentielles pour la mesure suprémale des ensembles sans produit. La preuve nécessite d'établir préalablement une borne inférieure sur la dimension des représentations non-triviales des groupes finis $SL_k(\mathbb{Z}/(p^n\mathbb{Z}))$ et $Sp_{2k}(\mathbb{Z}/(p^n\mathbb{Z}))$. Notre théoréme prolonge le travail de Landazuri et Seitz, qui considérent le degré minimal des représentations pour les groupes de Chevalley sur les corps finis, tout en offrant une preuve plus simple que la leur. La seconde partie de la thése à trait à la théorie algébrique des nombres. Un polynome monogéne $f$ est un polynome unitaire irréductible à coefficients entiers qui endengre un corps de nombres monogéne. Pour un nombre premier $q$ donné, nous allons montrer, en utilisant le théoréme de densité de Tchebotariov, que la densité des nombres premiers $p$ tels que $t^q -p$ soit monogéne est supérieure ou égale à $(q-1)/q$. Nous allons également démontrer que, quand $q=3$, la densité des nombres premiers $p$ tels que $\mathbb{Q}(\sqrt[3]{p})$ soit non monogéne est supérieure ou égale à $1/9$.

Simulation-Based Finite-Sample Tests for Heteroskedasticity and ARCH Effects.

A wide range of tests for heteroskedasticity have been proposed in the econometric and statistics literature. Although a few exact homoskedasticity tests are available, the commonly employed procedures are quite generally based on asymptotic approximations which may not provide good size control in finite samples. There has been a number of recent studies that seek to improve the reliability of common heteroskedasticity tests using Edgeworth, Bartlett, jackknife and bootstrap methods. Yet the latter remain approximate. In this paper, we describe a solution to the problem of controlling the size of homoskedasticity tests in linear regression contexts. We study procedures based on the standard test statistics [e.g., the Goldfeld-Quandt, Glejser, Bartlett, Cochran, Hartley, Breusch-Pagan-Godfrey, White and Szroeter criteria] as well as tests for autoregressive conditional heteroskedasticity (ARCH-type models). We also suggest several extensions of the existing procedures (sup-type of combined test statistics) to allow for unknown breakpoints in the error variance. We exploit the technique of Monte Carlo tests to obtain provably exact p-values, for both the standard and the new tests suggested. We show that the MC test procedure conveniently solves the intractable null distribution problem, in particular those raised by the sup-type and combined test statistics as well as (when relevant) unidentified nuisance parameter problems under the null hypothesis. The method proposed works in exactly the same way with both Gaussian and non-Gaussian disturbance distributions [such as heavy-tailed or stable distributions]. The performance of the procedures is examined by simulation. The Monte Carlo experiments conducted focus on : (1) ARCH, GARCH, and ARCH-in-mean alternatives; (2) the case where the variance increases monotonically with : (i) one exogenous variable, and (ii) the mean of the dependent variable; (3) grouped heteroskedasticity; (4) breaks in variance at unknown points. We find that the proposed tests achieve perfect size control and have good power.

Finite-Sample Diagnostics for Multivariate Regressions with Applications to Linear Asset Pricing Models

In this paper, we propose several finite-sample specification tests for multivariate linear regressions (MLR) with applications to asset pricing models. We focus on departures from the assumption of i.i.d. errors assumption, at univariate and multivariate levels, with Gaussian and non-Gaussian (including Student t) errors. The univariate tests studied extend existing exact procedures by allowing for unspecified parameters in the error distributions (e.g., the degrees of freedom in the case of the Student t distribution). The multivariate tests are based on properly standardized multivariate residuals to ensure invariance to MLR coefficients and error covariances. We consider tests for serial correlation, tests for multivariate GARCH and sign-type tests against general dependencies and asymmetries. The procedures proposed provide exact versions of those applied in Shanken (1990) which consist in combining univariate specification tests. Specifically, we combine tests across equations using the MC test procedure to avoid Bonferroni-type bounds. Since non-Gaussian based tests are not pivotal, we apply the “maximized MC” (MMC) test method [Dufour (2002)], where the MC p-value for the tested hypothesis (which depends on nuisance parameters) is maximized (with respect to these nuisance parameters) to control the test’s significance level. The tests proposed are applied to an asset pricing model with observable risk-free rates, using monthly returns on New York Stock Exchange (NYSE) portfolios over five-year subperiods from 1926-1995. Our empirical results reveal the following. Whereas univariate exact tests indicate significant serial correlation, asymmetries and GARCH in some equations, such effects are much less prevalent once error cross-equation covariances are accounted for. In addition, significant departures from the i.i.d. hypothesis are less evident once we allow for non-Gaussian errors.

The role of NHL-2 in regulating C.elegans P granule function

La divison cellulaire asymétrique est un processus essentiel qui permet aux cellules souches de s’auto-renouveller et de produire une cellule fille destinée à la différenciation. La lignée germinale de C. elegans, totipotente et immortelle, est une lignée de cellules souches qui contient des organites ribonucléoprotéiques appelés granules P. Au cours du développement ces derniers sont toujours localisés spécifiquement dans les cellules précurseurs de la lignée germinals, suggérant qu’ils sont des déterminants de la lignée germinale. De façon intéressante, des granules ribonucléoprotéiques, comme les P bodies impliqués dans le contrôle post-transcriptionnel, ont été observés chez tous les organismes. Néanmoins, la fonction précise des granules P de C. elegans est inconnue. Récemment, notre laboratoire a montré que NHL-2, un homologue de Mei-P26 de Drosophile, colocalise avec les granules P dans des embryons précoces et joue un rôle dans la division cellulaire asymétrique et dans la polarité cellulaire. Tous les granules P contiennent NHL- 2, ce qui nous a mené à poser l’hypothèse que NHL-2 régule la biogenèse et la fonction des granules P. Nous avons testé cette hypothèse par imagerie et quantification de l'intensité de PGL-1, un composant essentiel des granules P, dans des embryons fixés. Nos résultats montrent que dans des embryons mutants pour nhl-2 il y a une réduction du nombre de granules P, de l'intensité de fluorescence moyenne (IFM) et de l'intensité de fluorescence total (IFT) de PGL-1. Une analyse plus poussée a montré qu'il existe deux populations distinctes d’embryons mutants pour nhl-2 : l’une présente une intensité de PGL-1 comparable à celle d’une population sauvage alors que le second groupe présente une forte réduction des quantités de PGL-1 et est comparable à des mutants pour pgl-1. Cette variabilité est aussi observée dans le phénotype de stérilité de nhl-2 mutant à des températures élevées. Globalement, nos résultats suggèrent que la perte de fonction de NHL-2 perturbe la prolifération des cellules germinales ainsi que la formation et/ou la stabilité des granules P au cours des étapes précoces du développement des précurseurs de la lignée germinals. D’autre part, ils suggèrent que la fonction de NHL-2 pourrait être partiellement redondants avec les autres régulateurs de la stabilité des granules P. Mots-clés : Granules P, NHL-2, Cellules germinals.

Évaluation de la densité osseuse péri acétabulaire après resurfaçage versus prothèse totale de la hanche métal-métal non cimentée

Ce mémoire présente l’évaluation du remodelage osseux autour des composantes acétabulaires non cimentées press-fit d’une arthroplastie de resurfaçage (RH) et d’une prothèse totale de hanche (PTH) après un minimum de 21 mois d’implantation. Nous avons mesuré par l’absorptiométrie à rayons X en double énergie (DEXA) la densité minérale osseuse (DMO) supra acétabulaire chez 60 patients (44 RH, 16 PTH). Aucune différence significative de la moyenne des DMO au niveau de la zone globale et de la zone centrale de l’acétabulum n’a été trouvée entre la hanche opérée et la hanche controlatérale, dans les deux groupes de traitement. Cependant, la DMO des zones corticospongieuses médiale et latérale est plus élevée du côté opéré par rapport au côté non opéré avec la cupule en chrome cobalt de la RH; (p=0,014 et 0,031 respectivement). Alors que pour la PTH avec une cupule en titane, la différence de la DMO au niveau de ces zones n’est pas significative; (p=0,130 et 0,733). Ces données semblent démontrer qu’avec des cupules plus rigides, il y a transfert des contraintes de charges vers la périphérie corticale. C’est la première étude à évaluer le remodelage osseux péri acétabulaire avec un RH. Cela montre que la DMO est relativement préservée et que le transfert des contraintes vers la périphérie peut être favorable au maintien de la stabilité de l’implant primaire et aux éventuelles révisions de la cupule press-fit du RH.