On Complexity of Lobbying in Multiple Referenda

In this paper we show that lobbying in conditions of “direct democracy” is virtually impossible, even in conditions of complete information about voters preferences, since it would require solving a very computationally hard problem. We use the apparatus of parametrized complexity for this purpose.

Quantum nonlocality, cryptography and complexity

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Network pricing problems : complexity, polyhedral study and solution approaches

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Interactive quantum information theory

La théorie de l'information quantique s'est développée à une vitesse fulgurante au cours des vingt dernières années, avec des analogues et extensions des théorèmes de codage de source et de codage sur canal bruité pour la communication unidirectionnelle. Pour la communication interactive, un analogue quantique de la complexité de la communication a été développé, pour lequel les protocoles quantiques peuvent performer exponentiellement mieux que les meilleurs protocoles classiques pour certaines tâches classiques. Cependant, l'information quantique est beaucoup plus sensible au bruit que l'information classique. Il est donc impératif d'utiliser les ressources quantiques à leur plein potentiel. Dans cette thèse, nous étudions les protocoles quantiques interactifs du point de vue de la théorie de l'information et étudions les analogues du codage de source et du codage sur canal bruité. Le cadre considéré est celui de la complexité de la communication: Alice et Bob veulent faire un calcul quantique biparti tout en minimisant la quantité de communication échangée, sans égard au coût des calculs locaux. Nos résultats sont séparés en trois chapitres distincts, qui sont organisés de sorte à ce que chacun puisse être lu indépendamment. Étant donné le rôle central qu'elle occupe dans le contexte de la compression interactive, un chapitre est dédié à l'étude de la tâche de la redistribution d'état quantique. Nous prouvons des bornes inférieures sur les coûts de communication nécessaires dans un contexte interactif. Nous prouvons également des bornes atteignables avec un seul message, dans un contexte d'usage unique. Dans un chapitre subséquent, nous définissons une nouvelle notion de complexité de l'information quantique. Celle-ci caractérise la quantité d'information, plutôt que de communication, qu'Alice et Bob doivent échanger pour calculer une tâche bipartie. Nous prouvons beaucoup de propriétés structurelles pour cette quantité, et nous lui donnons une interprétation opérationnelle en tant que complexité de la communication quantique amortie. Dans le cas particulier d'entrées classiques, nous donnons une autre caractérisation permettant de quantifier le coût encouru par un protocole quantique qui oublie de l'information classique. Deux applications sont présentées: le premier résultat général de somme directe pour la complexité de la communication quantique à plus d'une ronde, ainsi qu'une borne optimale, à un terme polylogarithmique près, pour la complexité de la communication quantique avec un nombre de rondes limité pour la fonction « ensembles disjoints ». Dans un chapitre final, nous initions l'étude de la capacité interactive quantique pour les canaux bruités. Étant donné que les techniques pour distribuer de l'intrication sont bien étudiées, nous nous concentrons sur un modèle avec intrication préalable parfaite et communication classique bruitée. Nous démontrons que dans le cadre plus ardu des erreurs adversarielles, nous pouvons tolérer un taux d'erreur maximal de une demie moins epsilon, avec epsilon plus grand que zéro arbitrairement petit, et ce avec un taux de communication positif. Il s'ensuit que les canaux avec bruit aléatoire ayant une capacité positive pour la transmission unidirectionnelle ont une capacité positive pour la communication interactive quantique. Nous concluons avec une discussion de nos résultats et des directions futures pour ce programme de recherche sur une théorie de l'information quantique interactive.

On Space-Time Trade-Off for Montgomery Multipliers over Finite Fields

La multiplication dans le corps de Galois à 2^m éléments (i.e. GF(2^m)) est une opérations très importante pour les applications de la théorie des correcteurs et de la cryptographie. Dans ce mémoire, nous nous intéressons aux réalisations parallèles de multiplicateurs dans GF(2^m) lorsque ce dernier est généré par des trinômes irréductibles. Notre point de départ est le multiplicateur de Montgomery qui calcule A(x)B(x)x^(-u) efficacement, étant donné A(x), B(x) in GF(2^m) pour u choisi judicieusement. Nous étudions ensuite l'algorithme diviser pour régner PCHS qui permet de partitionner les multiplicandes d'un produit dans GF(2^m) lorsque m est impair. Nous l'appliquons pour la partitionnement de A(x) et de B(x) dans la multiplication de Montgomery A(x)B(x)x^(-u) pour GF(2^m) même si m est pair. Basé sur cette nouvelle approche, nous construisons un multiplicateur dans GF(2^m) généré par des trinôme irréductibles. Une nouvelle astuce de réutilisation des résultats intermédiaires nous permet d'éliminer plusieurs portes XOR redondantes. Les complexités de temps (i.e. le délais) et d'espace (i.e. le nombre de portes logiques) du nouveau multiplicateur sont ensuite analysées: 1. Le nouveau multiplicateur demande environ 25% moins de portes logiques que les multiplicateurs de Montgomery et de Mastrovito lorsque GF(2^m) est généré par des trinômes irréductible et m est suffisamment grand. Le nombre de portes du nouveau multiplicateur est presque identique à celui du multiplicateur de Karatsuba proposé par Elia. 2. Le délai de calcul du nouveau multiplicateur excède celui des meilleurs multiplicateurs d'au plus deux évaluations de portes XOR. 3. Nous determinons le délai et le nombre de portes logiques du nouveau multiplicateur sur les deux corps de Galois recommandés par le National Institute of Standards and Technology (NIST). Nous montrons que notre multiplicateurs contient 15% moins de portes logiques que les multiplicateurs de Montgomery et de Mastrovito au coût d'un délai d'au plus une porte XOR supplémentaire. De plus, notre multiplicateur a un délai d'une porte XOR moindre que celui du multiplicateur d'Elia au coût d'une augmentation de moins de 1% du nombre total de portes logiques.

The role of mechanistic target of rapamycin (mTOR) pathway and synaptic protein GABAA-R in cortical GABAergic cell connectivity

Quelque 30 % de la population neuronale du cortex mammalien est composée d’une population très hétérogène d’interneurones GABAergiques. Ces interneurones diffèrent quant à leur morphologie, leur expression génique, leurs propriétés électrophysiologiques et leurs cibles subcellulaires, formant une riche diversité. Après leur naissance dans les éminences ganglioniques, ces cellules migrent vers les différentes couches corticales. Les interneurones GABAergiques corticaux exprimant la parvalbumin (PV), lesquels constituent le sous-type majeur des interneurones GABAergiques, ciblent spécifiquement le soma et les dendrites proximales des neurones principaux et des neurones PV+. Ces interneurones sont nommés cellules à panier (Basket Cells –BCs) en raison de la complexité morphologique de leur axone. La maturation de la connectivité distincte des BCs PV+, caractérisée par une augmentation de la complexité de l’axone et de la densité synaptique, se déroule graduellement chez la souris juvénile. Des travaux précédents ont commencé à élucider les mécanismes contrôlant ce processus de maturation, identifiant des facteurs génétiques, l’activité neuronale ainsi que l’expérience sensorielle. Cette augmentation marquante de la complexité axonale et de la synaptogénèse durant cette phase de maturation suggère la nécessité d’une synthèse de protéines élevée. La voie de signalisation de la cible mécanistique de la rapamycine (Mechanistic Target Of Rapamycin -mTOR) a été impliquée dans le contrôle de plusieurs aspects neurodéveloppementaux en régulant la synthèse de protéines. Des mutations des régulateurs Tsc1 et Tsc2 du complexe mTOR1 causent la sclérose tubéreuse (TSC) chez l’humain. La majorité des patients TSC développent des problèmes neurologiques incluant des crises épileptiques, des retards mentaux et l’autisme. D’études récentes ont investigué le rôle de la dérégulation de la voie de signalisation de mTOR dans les neurones corticaux excitateurs. Toutefois, son rôle dans le développement des interneurones GABAergiques corticaux et la contribution spécifique de ces interneurones GABAergiques altérés dans les manifestations de la maladie demeurent largement inconnus. Ici, nous avons investigué si et comment l’ablation du gène Tsc1 perturbe le développement de la connectivité GABAergique, autant in vitro que in vivo. Pour investiguer le rôle de l’activation de mTORC1 dans le développement d’une BC unique, nous avons délété le gène Tsc1 en transfectant CRE-GFP dirigé par un promoteur spécifique aux BCs dans des cultures organotypiques provenant de souris Tsc1lox. Le knockdown in vitro de Tsc1 a causé une augmentation précoce de la densité des boutons et des embranchements terminaux formés par les BCs mutantes, augmentation renversée par le traitement à la rapamycine. Ces données suggèrent que l’hyperactivation de la voie de signalisation de mTOR affecte le rythme de la maturation des synapses des BCs. Pour investiguer le rôle de mTORC1 dans les interneurones GABAergiques in vivo, nous avons croisé les souris Tsc1lox avec les souris Nkx2.1-Cre et PV-Cre. À P18, les souris Tg(Nkx2.1-Cre);Tsc1flox/flox ont montré une hyperactivation de mTORC1 et une hypertrophie somatique des BCs de même qu’une augmentation de l’expression de PV dans la région périsomatique des neurones pyramidaux. Au contraire, à P45 nous avons découvert une réduction de la densité des punctas périsomatiques PV-gephyrin (un marqueur post-synaptique GABAergique). L’étude de la morphologie des BCs en cultures organotypiques provenant du knock-out conditionnel Nkx2.1-Cre a confirmé l’augmentation initiale du rythme de maturation, lequel s’effondre ensuite aux étapes développementales tardives. De plus, les souris Tg(Nkx2.1Cre);Tsc1flox/flox montrent des déficits dans la mémoire de travail et le comportement social et ce d’une façon dose-dépendante. En somme, ces résultats suggèrent que l’activation contrôlée de mTOR régule le déroulement de la maturation et la maintenance des synapses des BCs. Des dysfonctions de la neurotransmission GABAergique ont été impliquées dans des maladies telles que l’épilepsie et chez certains patients, elles sont associées avec des mutations du récepteur GABAA. De quelle façon ces mutations affectent le processus de maturation des BCs demeuret toutefois inconnu. Pour adresser cette question, nous avons utilisé la stratégie Cre-lox pour déléter le gène GABRA1, codant pour la sous-unité alpha-1 du récepteur GABAA dans une unique BC en culture organotypique. La perte de GABRA1 réduit l’étendue du champ d’innervation des BCs, suggérant que des variations dans les entrées inhibitrices en raison de l’absence de la sous-unité GABAAR α1 peuvent affecter le développement des BCs. La surexpression des sous-unités GABAAR α1 contenant des mutations identifiées chez des patients épileptiques ont montré des effets similaires en termes d’étendue du champ d’innervation des BCs. Pour approfondir, nous avons investigué les effets de ces mutations identifiées chez l’humain dans le développement des épines des neurones pyramidaux, lesquelles sont l’endroit privilégié pour la formation des synapses excitatrices. Somme toute, ces données montrent pour la première fois que différentes mutations de GABRA1 associées à des syndromes épileptiques peuvent affecter les épines dendritiques et la formation des boutons GABAergiques d’une façon mutation-spécifique.