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.

Essays in economics of information

Cette thèse est une collection de trois articles en économie de l'information. Le premier chapitre sert d'introduction et les Chapitres 2 à 4 constituent le coeur de l'ouvrage. Le Chapitre 2 porte sur l’acquisition d’information sur l’Internet par le biais d'avis de consommateurs. En particulier, je détermine si les avis laissés par les acheteurs peuvent tout de même transmettre de l’information à d’autres consommateurs, lorsqu’il est connu que les vendeurs peuvent publier de faux avis à propos de leurs produits. Afin de comprendre si cette manipulation des avis est problématique, je démontre que la plateforme sur laquelle les avis sont publiés (e.g. TripAdvisor, Yelp) est un tiers important à considérer, autant que les vendeurs tentant de falsifier les avis. En effet, le design adopté par la plateforme a un effet indirect sur le niveau de manipulation des vendeurs. En particulier, je démontre que la plateforme, en cachant une partie du contenu qu'elle détient sur les avis, peut parfois améliorer la qualité de l'information obtenue par les consommateurs. Finalement, le design qui est choisi par la plateforme peut être lié à la façon dont elle génère ses revenus. Je montre qu'une plateforme générant des revenus par le biais de commissions sur les ventes peut être plus tolérante à la manipulation qu'une plateforme qui génère des revenus par le biais de publicité. Le Chapitre 3 est écrit en collaboration avec Marc Santugini. Dans ce chapitre, nous étudions les effets de la discrimination par les prix au troisième degré en présence de consommateurs non informés qui apprennent sur la qualité d'un produit par le biais de son prix. Dans un environnement stochastique avec deux segments de marché, nous démontrons que la discrimination par les prix peut nuire à la firme et être bénéfique pour les consommateurs. D'un côté, la discrimination par les prix diminue l'incertitude à laquelle font face les consommateurs, c.-à-d., la variance des croyances postérieures est plus faible avec discrimination qu'avec un prix uniforme. En effet, le fait d'observer deux prix (avec discrimination) procure plus d'information aux consommateurs, et ce, même si individuellement chacun de ces prix est moins informatif que le prix uniforme. De l'autre côté, il n'est pas toujours optimal pour la firme de faire de la discrimination par les prix puisque la présence de consommateurs non informés lui donne une incitation à s'engager dans du signaling. Si l'avantage procuré par la flexibilité de fixer deux prix différents est contrebalancé par le coût du signaling avec deux prix différents, alors il est optimal pour la firme de fixer un prix uniforme sur le marché. Finalement, le Chapitre 4 est écrit en collaboration avec Sidartha Gordon. Dans ce chapitre, nous étudions une classe de jeux où les joueurs sont contraints dans le nombre de sources d'information qu'ils peuvent choisir pour apprendre sur un paramètre du jeu, mais où ils ont une certaine liberté quant au degré de dépendance de leurs signaux, avant de prendre une action. En introduisant un nouvel ordre de dépendance entre signaux, nous démontrons qu'un joueur préfère de l'information qui est la plus dépendante possible de l'information obtenue par les joueurs pour qui les actions sont soit, compléments stratégiques et isotoniques, soit substituts stratégiques et anti-toniques, avec la sienne. De même, un joueur préfère de l'information qui est la moins dépendante possible de l'information obtenue par les joueurs pour qui les actions sont soit, substituts stratégiques et isotoniques, soit compléments stratégiques et anti-toniques, avec la sienne. Nous établissons également des conditions suffisantes pour qu'une structure d'information donnée, information publique ou privée par exemple, soit possible à l'équilibre.

Theory and numerical integration of subsurface light transport

En synthèse d’images, reproduire les effets complexes de la lumière sur des matériaux transluminescents, tels que la cire, le marbre ou la peau, contribue grandement au réalisme d’une image. Malheureusement, ce réalisme supplémentaire est couteux en temps de calcul. Les modèles basés sur la théorie de la diffusion visent à réduire ce coût en simulant le comportement physique du transport de la lumière sous surfacique tout en imposant des contraintes de variation sur la lumière incidente et sortante. Une composante importante de ces modèles est leur application à évaluer hiérarchiquement l’intégrale numérique de l’illumination sur la surface d’un objet. Cette thèse révise en premier lieu la littérature actuelle sur la simulation réaliste de la transluminescence, avant d’investiguer plus en profondeur leur application et les extensions des modèles de diffusion en synthèse d’images. Ainsi, nous proposons et évaluons une nouvelle technique d’intégration numérique hiérarchique utilisant une nouvelle analyse fréquentielle de la lumière sortante et incidente pour adapter efficacement le taux d’échantillonnage pendant l’intégration. Nous appliquons cette théorie à plusieurs modèles qui correspondent à l’état de l’art en diffusion, octroyant une amélioration possible à leur efficacité et précision.

Régulation de la division asymétrique chez C. elegans

La division asymétrique est essentielle pour générer la diversité au cours du développement et permet aussi de réguler la balance entre renouvellement et différenciation des cellules souches chez l’adulte. Dans ces deux cas de figure, elle dépend respectivement d’une polarité intrinsèque ou d’une polarité extrinsèque. C. elegans est un excellent modèle pour étudier les mécanismes cellulaires et moléculaires de la division asymétrique in vivo. Chez l’embryon, le maintien d’un axe de polarité antéro-postérieur dépend des protéines PAR conservées et localisées de façon asymétrique en deux groupes mutuellement exclusifs; le groupe antérieur avec PAR-3, PAR-6, PKC-3 et le groupe postérieur avec PAR-2 et PAR-1. L’absence d’une protéine PAR entraine une perte de polarité et une létalité embryonnaire. Lors d’un crible par ARN interférence mené par Jean-Claude Labbé pour identifier les suppresseurs de la létalité associée à la perte de PAR-2, deux cyclines de type B, CYB-2.1 et CYB-2.2 ont été trouvées. J’ai déterminé que CYB-2.1 et CYB-2.2 interviennent dans la polarité sans perturber le cycle cellulaire et agissent vraisemblablement avec leur kinase associée, CDK-1, pour stabiliser les niveaux protéiques de PAR-6. Ces travaux permettent de mieux définir les liens étroits entre polarité et cycle cellulaire. La lignée germinale de C. elegans est un excellent modèle pour étudier les divisions des cellules souches germinales in vivo. Par contre, l’absence d’orientation préférentielle de ces divisions laisse envisager que la complexité morphologique de la niche pourrait engendrer une diversité d’axe possible. J’ai étudié la régulation morphologique de cette niche, une unique cellule somatique appelée distal tip cell (DTC), qui arborise de longues extensions au stade adulte. Mes résultats préliminaires favorisent un modèle dans lequel les cellules souches et progéniteurs germinaux (CSPG) supportent la formation de ces extensions. Enfin, j’ai obtenu des conditions favorables à l’étude de la division asymétrique extrinsèque dans ce modèle, en simplifiant l’architecture de la niche dans des conditions qui préservent les divisions cellulaires des cellules souches. Mes travaux ont permis de mieux comprendre les liens unissant les différents processus biologiques impliqués dans la division asymétrique, d’une part par l’étude du rôle qu’y jouent des régulateurs clés du cycle cellulaire au cours du développement et d’autre part par la caractérisation d’une communication bidirectionnelle entre la niche et les cellules souches chez l’adulte.

Altérations synaptiques à la jonction neuromusculaire dans un modèle murin de sclérose latérale amyotrophique

La sclérose latérale amyotrophique est une maladie neurodégénérative fatale caractérisée par la dégénérescence progressive des neurones moteurs centraux et périphériques. L’un des premiers signes de la maladie est la dénervation de la jonction neuromusculaire (JNM). Les diverses unités motrices (UM) ne présentent toutefois pas la même vulnérabilité à la dénervation dans la SLA: les UM rapide fatigables sont en fait les plus vulnérables et les UM lentes sont les plus résistantes. Alors que des études précédentes ont démontré dans plusieurs modèles animaux de la SLA de nombreuses variations synaptiques, les découvertes ont été contradictoires. Par ailleurs, le type d’UM n’a pas été tenu en compte dans ces divers travaux. Nous avons donc émis l’hypothèse que la présence de la mutation SOD1 pourrait affecter différemment la transmission synaptique des UM, en accord avec leur vulnérabilité sélective. En effectuant des enregistrements électrophysiologiques et de l’immunohistochimie, nous avons étudié la transmission synaptique des différents types d’UM du muscle à contraction rapide Extensor Digitorum Longus (EDL; rapide fatigable (FF) MU) et du muscle à contraction lente Soleus (SOL; lente (S) and rapide fatigue-résistante (FR) MU) de la souris SOD1G37R et leur congénères WT. Pour identifier le type d’UM, un marquage par immunohistochimie des chaînes de myosine a été effectué. Un triple marquage de la JNM a également été effectué pour vérifier son intégrité aux différents stades de la maladie. À P160, dans la période asymptomatique de la maladie, alors qu’aucune altération morphologique n’était présente, l’activité évoquée était déjà altérée différemment en fonction des UM. Les JNMs FF mutantes ont démontré une diminution de l’amplitude des potentiels de plaque motrice (PPM) et du contenu quantique, alors que les JNMs lentes démontraient pratiquement le contraire. Les JNMs FR montraient quant à elles une force synaptique semblable au WT. À P380, dans la période présymtomatique, de nombreuses altérations morphologiques ont été observées dans le muscle EDL, incluant la dénervation complète, l’innervation partielle et les extensions du nerf. La transmission synaptique évoquée des UM FF étaient toujours réduites, de même que la fréquence des potentiels de plaque motrice miniatures. À P425, à l’apparition des premiers symptômes, l’activité synaptique des JNMs S était redevenue normale alors que les JNMs FR ont montré à ce moment une diminution du contenu quantique par rapport au contrôle. De manière surprenante, aucun changement du ratio de facilitation n’a été observé malgré les changements flagrants de la force synaptique. Ces résultats révèlent que la fonction de la JNM est modifiée différemment en fonction de la susceptibilité des UM dans l’ALS. Cette étude fournit des pistes pour une meilleure compréhension de la physiologie de la JNM durant la pathologie qui est cruciale au développement d’une thérapie adéquate ciblant la JNM dans la SLA.

Ranking by rating

Each item in a given collection is characterized by a set of possible performances. A (ranking) method is a function that assigns an ordering of the items to every performance profile. Ranking by Rating consists in evaluating each item’s performance by using an exogenous rating function, and ranking items according to their performance ratings. Any such method is separable: the ordering of two items does not depend on the performances of the remaining items. We prove that every separable method must be of the ranking-by-rating type if (i) the set of possible performances is the same for all items and the method is anonymous, or (ii) the set of performances of each item is ordered and the method is monotonic. When performances are m-dimensional vectors, a separable, continuous, anonymous, monotonic, and invariant method must rank items according to a weighted geometric mean of their performances along the m dimensions.

Ordinally consistent tournament solutions

A set ranking method assigns to each tournament on a given set an ordering of the subsets of that set. Such a method is consistent if (i) the items in the set are ranked in the same order as the sets of items they beat and (ii) the ordering of the items fully determines the ordering of the sets of items. We describe two consistent set ranking methods.