Communication complexity : large output functions, partition bounds, and quantum nonlocality
Complexité de la communication : fonctions à grande sortie, bornes partitions et non-localité quantique
par Alexandre NOLIN sous la direction de Sophie LAPLANTE
Thèse de doctorat en Informatique
ED 386 Sciences Mathematiques de Paris Centre

Soutenue le jeudi 26 novembre 2020 à Université de Paris (2019-....)

Sujets
  • Distribution (théorie des probabilités)
  • Inégalités de Bell

Les thèses de doctorat soutenues à Université de Paris sont déposées au format électronique

Consultation de la thèse sur d’autres sites :

TEL (Version intégrale de la thèse (pdf))

Description en anglais
Description en français
Mots clés
Complexité de la communication, Bornes partition, Non-localité quantique, Complexité de l'information, Fonctions non-Booléennes
Resumé
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.