Français Anglais
Accueil Annuaire Plan du site
Accueil > Production scientifique > Thèses et habilitations
Production scientifique
Doctorat de

Doctorat
Equipe : Algorithmique et Complexité

" Méthodes combinatoires et algébriques en complexité de la communication."

Début le 01/10/2005
Direction : LAPLANTE, Sophie

Ecole doctorale : Paris XI
Etablissement d'inscription : Université Paris-Saclay

Lieu de déroulement : LRI

Soutenue le 28/09/2009 devant le jury composé de :

Activités de recherche :

Résumé :
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.