La théorie de la complexité de communication étudie le coût minimum de communication nécessaire pour évaluer une fonction lorsque les entrées sont distribuées parmi plusieurs entités. Deux modèles qui sont bien étudiés sont les modèles d'erreur bornée et d'erreur non-bornée, où les entités peuvent profiter de l'aléatoire pour faciliter leurs calculs. Les premiers résultats dans ce domaine montrèrent que la fonction Égalité peut être calculée avec un coût minimal dans des deux modèles aléatoires, tandis qu'elle atteint le coût maximal dans le modèle déterministe. Ceci démontre le pouvoir de l'aléatoire dans la communication, par opposition à des autres modèles de computation, tels que les arbres de décision.Le fait que l'Égalité présente la séparation maximale entre les efficacités de communication aléatoire et déterministe incite la recherche d'un modèle hybride de communication : un modèle déterministe avec accès à un oracle d'Égalité, où l'on remplace la sélection au hasard avec un pouvoir omniscient qui calcule l'Égalité de manière efficace. Un résultat clé concernant ce modèle d'oracle démontre que le pouvoir de la sélection aléatoire n'est pas entièrement reflété par la capacité de calculer l'Égalité efficacement, ce qui fait ce modèle intéressant à étudier.Un sujet fondamental dans la théorie de la complexité est la comparaison des puissances relatives des différents modèles. Les résultats sur les puissances peuvent être classifiés en trois catégories principales : séparation — quand un modèle est plus fort qu'un autre, inclusion — quand le critère d'efficacité d'un modèle est contenu dans celui d'un autre, et structure — quand les fonctions que l'on peut calculer dans un modèle possèdent certaines propriétés qui correspondent à la simplicité de calcul.Malgré de la recherche extensive dans le domaine, plusieurs questions fondamentales à propos de ces trois modèles ne sont toujours pas résolues. Le manque d'exemples explicites limite sévèrement notre compréhension des résultats structurels. De plus, beaucoup des techniques actuellement connues pour établir des bornes inférieures sont trop faibles pour caractériser structurellement les fonctions avec complexité uniformément bornée.Cette thèse présente de nouveaux résultats de séparation et structurels dans la complexité de communication, ce qui représente un avancement vers la résolution de ces problèmes ouverts reliés aux régimes de coût constant. On démontre que nos résultats de séparation fournissent des nouvelles séparations au-delà de la théorie de la complexité de communication : ils impliquent des séparations dans les domaines de la théorie d'apprentissage et la théorie de la complexité des requêtes
La théorie de la complexité de communication étudie le coût minimum de communication nécessaire pour évaluer une fonction lorsque les entrées sont distribuées parmi plusieurs entités. Deux modèles qui sont bien étudiés sont les modèles d'erreur bornée et d'erreur non-bornée, où les entités peuvent profiter de l'aléatoire pour faciliter leurs calculs. Les premiers résultats dans ce domaine montrèrent que la fonction Égalité peut être calculée avec un coût minimal dans des deux modèles aléatoires, tandis qu'elle atteint le coût maximal dans le modèle déterministe. Ceci démontre le pouvoir de l'aléatoire dans la communication, par opposition à des autres modèles de computation, tels que les arbres de décision.Le fait que l'Égalité présente la séparation maximale entre les efficacités de communication aléatoire et déterministe incite la recherche d'un modèle hybride de communication : un modèle déterministe avec accès à un oracle d'Égalité, où l'on remplace la sélection au hasard avec un pouvoir omniscient qui calcule l'Égalité de manière efficace. Un résultat clé concernant ce modèle d'oracle démontre que le pouvoir de la sélection aléatoire n'est pas entièrement reflété par la capacité de calculer l'Égalité efficacement, ce qui fait ce modèle intéressant à étudier.Un sujet fondamental dans la théorie de la complexité est la comparaison des puissances relatives des différents modèles. Les résultats sur les puissances peuvent être classifiés en trois catégories principales : séparation — quand un modèle est plus fort qu'un autre, inclusion — quand le critère d'efficacité d'un modèle est contenu dans celui d'un autre, et structure — quand les fonctions que l'on peut calculer dans un modèle possèdent certaines propriétés qui correspondent à la simplicité de calcul.Malgré de la recherche extensive dans le domaine, plusieurs questions fondamentales à propos de ces trois modèles ne sont toujours pas résolues. Le manque d'exemples explicites limite sévèrement notre compréhension des résultats structurels. De plus, beaucoup des techniques actuellement connues pour établir des bornes inférieures sont trop faibles pour caractériser structurellement les fonctions avec complexité uniformément bornée.Cette thèse présente de nouveaux résultats de séparation et structurels dans la complexité de communication, ce qui représente un avancement vers la résolution de ces problèmes ouverts reliés aux régimes de coût constant. On démontre que nos résultats de séparation fournissent des nouvelles séparations au-delà de la théorie de la complexité de communication : ils impliquent des séparations dans les domaines de la théorie d'apprentissage et la théorie de la complexité des requêtes
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.
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 .
Complexité de la communication : fonctions à grande sortie, bornes partitions et non-localité quantique La plupart des problèmes étudiés en complexité de la communication sont Booléens. Pour des fonctions à plus large sortie, la manière dont le résultat du calcul doit être retourné – le modèle de sortie – peut grandement changer la complexité du problème. De même, les bornes inférieures ne s’appliquent pas toutes à tous les modèles. Dans cette thèse, nous étudions des bornes inférieures impactées par le modèle de sortie, revisitons quelques résultats classiques à la lumière de ces modèles de sortie, et les relions au formalisme des comportements et des inégalités de Bell du domaine de la non-localité quantique. Premièrement, nous nous intéressons aux bornes partition et montrons que leur application à une fonction à large sortie donne nécessairement de grandes valeurs, indiquant qu’elles ne sont des bornes inférieures que pour un de nos modèles de sortie. Nous montrons également comment construire un protocole déterministe à partir d’une solution optimale de la borne partition dite “positive”, ainsi qu’une nouvelle connexion avec une autre borne inférieure, la régularité faible. Via une récente réinterprétation de la borne partition en termes d’information, nous établissons une séparation exponentielle entre la borne partition et la complexité de la communication. Le problème permettant cette séparation est un problème récemment introduit pour séparer la complexité de la communication et la complexité de l’information dite “externe”. Ensuite, nous définissons plusieurs modèles de sortie. Nous les séparons, en montrant de grands écarts de complexités entre les différents modèles sur quelques problèmes. Nous re-prouvons dans nos modèles quelques résultats classiques de réduction d’erreur et de suppression d’aléatoire auparavant seulement connus pour les modèles de sortie les plus courants. Nous établissons pour quelques problèmes naturels supplémentaires que leur complexité varie significativement en selon le modèle de sortie, et montrons que la borne inférieure du rang s’applique toujours à nos modèles à une petite modification près. En dernier lieu, nous traitons de non-localité quantique et montrons que certaines bornes inférieures en complexité de la communication peuvent être interprétées sous la forme d’inégalités de Bell. Les inégalités de Bell obtenues sont résistantes à l’inefficacité de détection, et ne le sont pas a priori à d’autres formes de bruit. Nous reformulons le calcul d’une fonction dans un modèle de sortie spécifique en le calcul d’un comportement – une famille de distributions de probabilités indexées par les entrées possibles. Ceci nous permet d’utiliser les bornes efficacité comme des généralisations naturelles de la borne partition pour des modèles de sortie non-standards.
La complexité de la communication a été introduite en 1979 par Andrew Chi-Chi Yao. Elle est depuis devenue l'un des modèles de calcul les plus étudiés. L'objectif de celle-ci est d'étudier des problèmes dont les entrées sont distribuées entre plusieurs joueurs, en quantifiant la communication que ceux-ci doivent échanger. Nous utilisons d'abord la complexité de Kolmogorov, une caractérisation algorithmique de l'aléatoire, pour prouver des bornes inférieures sur la complexité de la communication. Notre méthode constitue une généralisation de la méthode d'incompressibilité. L'avantage de cette approche est de mettre en valeur la nature combinatoire des preuves. Nous étudions ensuite la simulation des distributions de probabilité causales avec de la communication. Ce modèle généralise la complexité de la communication traditionnelle et comprend en particulier les distributions quantiques. Nous montrons pour ce problème des bornes inférieures et supérieures. Dans le cas des fonctions booléennes, la borne inférieure que nous proposons est équivalente aux normes de factorisation, une puissante méthode introduite par Linial et Shraibman en 2006. Enfin, nous étudions la complexité en boîte non-locale. Cette ressource a été introduite par Popescu et Rohrlich pour étudier la non-localité. Le problème est de quantifier le nombre de boîtes nécessaire et suffisant pour calculer une fonction ou simuler une distributions. Nous donnons encore des bornes inférieures et supérieures pour ces problèmes, ainsi que des applications à l'évaluation sécurisée, un problème cryptographique très important.
Les mesures complexes à travers le prisme des jeux à deux joueurs et des signatures de l'hypercube Les mesures de complexité des fonctions booléennes capturent divers aspects de la difficulté du calcul d'une fonction et leur étude consiste à trouver des connexions entre différentes mesures de complexité. Dans la première partie de cette thèse, nous introduisons et étudions la complexité de jeux de certificats, une mesure de complexité basée sur la probabilité de gagner un jeu dans lequel deux joueurs reçoivent des entrées avec des valeurs de fonctions différentes et doivent produire un indice i pour lequel leurs entrées diffèrent, sans communiquer. Nous donnons des bornes supérieures et inférieures pour les stratégies à base de pièces privées, de pièces publiques, d'intrication partagée et de non-signalisation, et nous prouvons quelques résultats de séparations. D'une part, nous montrons que la complexité dans le cas des pièces publiques est majorée par les complexités de requête aléatoire et de certificat. D'autre part, nous montrons qu'elle est minorée par la complexité fractionnelle de certificat, ce qui en fait un bon candidat pour trouver des bornes inférieures fortes sur la complexité de requête aléatoire. La complexité dans le cas des pièces privées est minorée par la complexité de requête aléatoire à erreur nulle. Nous utilisons la non-signalisation, une notion d'information quantique, pour minorer par n la complexité de jeux de certificats quantiques de la fonction OR, dont la complexité de requête quantique est de Θ(√n), puis nous montrons que ce "goulot d'étranglement de non-signalisation" s'applique à toutes les fonctions à sensibilité, à sensibilité de bloc ou à sensibilité de bloc fractionnaire élevée. Nous considérons également la version mono-bit des jeux de certificats, où les entrées des deux joueurs sont restreints à une distance de Hamming de 1. Nous prouvons que la version mono-bit de la complexité de jeux de certificats avec aléa partagé est égale à la sensibilité à un facteur constant près, ce qui donne une nouvelle caractérisation de la sensibilité. D'autre part, la version mono-bit de la complexité de jeux de certificats avec aléa privé est égale à λ2, où λ est la sensibilité spectrale. Dans la deuxième partie de cette thèse, nous revisitons la célèbre preuve de la conjecture de la sensibilité par Hao Huang. En utilisant des techniques spectrales, Huang a prouvé que tout sous-graphe de l'hypercube Hn de dimension n induit sur plus de la moitié des sommets a un degré maximal d'au moins √n. Combiné avec des travaux antérieurs, ce résultat a complété une preuve de la conjecture de la sensibilité. Nous en donnons une preuve alternative en utilisant seulement la dépendance linéaire des vecteurs associés aux sommets de l'hypercube. Notre approche permet de mieux comprendre les propriétés structurelles du sous-graphe induit, en plus du plus grand degré. En particulier, nous prouvons que dans tout sous-graphe induit de Hn avec plus de la moitié du nombre de sommets, il existe deux sommets, l'un de parité impaire et l'autre de parité paire, chacun ayant au moins n sommets à une distance au plus égale à 2. Comme application, nous montrons que pour toute fonction booléenne f, le degré polynomial est majoré par le produit de la sensibilité 0 et de la sensibilité 1, s0(f)s1(f), une affirmation strictement plus forte qui implique le théorème de Huang. Nous obtenons également des relations structurelles pour les sous-graphes induits à distance 3. Un ingrédient clé de la preuve de Huang était des hypercubes signés avec la propriété que chaque cycle de longueur 4 est affecté d'un signe négatif. Nous examinons en détail cette signature et donnons une signature quasi-optimale qui utilise le nombre minimum de bords négatifs tout en garantissant que chaque cycle de longueur 4 est négatif. Ce problème s'avère être lié à l'un des problèmes d'Erdös sur le plus grand sous-graphe de l'hypercube exempt de 4-cycles.
Cette thèse se trouve à l'intersection de la théorie des matrices aléatoires, des probabilités libres et de la théorie de l'information quantique. La plus grande partie des travaux présentés se concentrent sur les aspects probabilistes de l'information quantique et, en particulier, sur l'usage des matrices aléatoires dans différents modèles en théorie quantique. Une autre partie de cette thèse est dédiée à la théorie des probabilités libres et à ses liens avec les matrices aléatoires et l'information quantique. En théorie quantique de l'information, il existe différents modèles de matrices densités aléatoires. On s'intéresse, dans l'esprit de la théorie des matrices aléatoires, au comportement asymptotique des matrices densités, dans la limite où la taille du système converge vers l'infini. Le point de vue pris dans cette thèse est celui des systèmes quantiques ouverts, où l'espace qui nous intéresse est couplé avec l'environnement et le système composé se trouve dans un état pur uniforme. En prenant la trace partielle sur l'environnement, on obtient des matrices densités aléatoires que l'on étudie dans deux régimes asymptotiques. En exploitant des liens avec l'ensemble des matrices aléatoires dites de Wishart, on obtient les densités spectrales limites et les fluctuations des valeurs propres extrémales. En collaboration avec Clément Pellegrini, on étudie des interactions répétées entre un système quantique et une chaîne de systèmes auxiliaires. Nous avons introduit des éléments aléatoires dans ce modèle, soit en considérant que les états de la chaîne sont des variables indépendantes et identiquement distribuées, soit en choisissant, à chaque interaction, une matrice unitaire d'interaction aléatoire uniforme. On s'intéresse aux propriétés asymptotiques des matrices, après un grand nombre d'interactions. Au passage, on introduit un nouveau modèle de matrices densités aléatoires que l'on compare avec les modèles existants dans la littérature. Un problème qui occupe une place centrale dans cette thèse est la conjecture de Nielsen sur la catalyse en théorie quantique de l'information. En collaboration avec Guillaume Aubrun, nous avons progressé vers la preuve de cette conjecture et nous l'avons par la suite généralisée dans différentes directions. L'outil principal utilisé dans ces travaux nous vient de la théorie des probabilités : la théorie des grandes déviations nous permet de comparer stochastiquement des puissances de convolution des mesures de probabilités. Les techniques introduites et le lien avec la théorie des grandes déviations nous ont permis de voir ce problème sous un autre angle et de donner aux théoriciens de l'information quantique un outil de travail puissant. Enfin, toujours en lien avec les matrices aléatoires, cette thèse a donné lieu à deux travaux en probabilités libres. Les ensembles de matrices aléatoires sont des exemples importants et simples où l'on peut observer l'indépendance libre; il est donc naturel de se demander s'il est possible d'obtenir la notion de liberté avec des matrices déterministes. Une telle construction a été proposée par Philippe Biane, en utilisant des sommes de transpositions dans l'algèbre du groupe symétrique. Avec Florent Benaych-Georges, on a pu généraliser les résultats de P. Biane à des cycles quelconques. Notre approche est combinatoire ce qui nous a permis d'aboutir à des formules explicites pour les moments et les cumulants libres des variables à la limite. Grâce à cette même approche nous avons élaboré un modèle analogue en probabilités classiques en remplaçant le groupe symétrique par le groupe abélien des parties d'un ensemble fini, muni de l'opération de différence symétrique. En collaboration avec Stéphane Attal, nous avons construit une approximation de l'espace de Fock libre (qui joue un rôle central en théorie des probabilités non-commutatives) par un produit libre dénombrable d'espaces discrets. Cette idée généralise au cas libre une construction similaire pour l'espace de Fock symétrique, introduite et étudié par S. Attal. En même temps nous avons obtenu une approximation des opérateurs fondamentaux de création, d'annihilation et de jauge par des opérateurs construits à partir des matrices de taille 2. En utilisant ces constructions sont ensuite utilisées pour retrouver quelques approximations connues du mouvement brownien libre et du processus de Poisson libre. Tous ces résultats se généralisent au cas des espaces de Fock de multiplicité supérieure, qui permettent d'approcher des processus multidimensionnels. En conclusion, l'ensemble des travaux scientifiques présentés dans cette thèse se situe à l'intersection de trois grandes directions: les matrices aléatoires, les probabilités libres et la théorie quantique de l'information, l'accent étant mis sur les interactions et sur les liens entre ces domaines.