Décision et vérification distribuées locales
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
This thesis lays in the context of distributed computing on networks, and more par-ticularly on the locality aspects that appear in that context. By the systematic study of decision problems, we introduce the complexity classes ULD and UNLD for local decision and verification respectively, and give separation results describing a hier¬archy involving other classes of local decision in the literature. These results are accompanied by a classification of several distributed problems based on the hierar¬chy we introduce. We examine and discuss two key ingredients in local decision and verification: the interpretation function on the outputs, and node identification. In this thesis, we also isolate the aspect of locality by studying it through the prism of the non-signaling model, which, even though not realistic, offers interest¬ing theoretical possibilities, including the derivation of lower bounds for distributed quantum computing without having to manipulate objects of that theory. Finally, by placing ourselves at the extreme limit of locality constraints, we consider the par¬ticular class of two-player games in absence of any communication and examine the limits of quantum distributed computing for this class of games.
Abstract FR:
Cette thèse s'inscrit dans le contexte du calcul distribué sur les réseaux, et, plus particulièrement, sur les aspects de localité qui apparaissent dans ce cadre. Par l'étude systématique des problèmes de décision, nous introduisons les classes de com¬plexité ULD et UNLD pour la décision et la vérification locale, et présentons des résultats de séparation décrivant une hiérarchie impliquant d'autres classes relatives à la littérature de la décision locale. Ces résultats sont accompagnés de la classifica¬tion de plusieurs problèmes distribués selon la hiérarchie introduite. Nous examinons et discutons dans ce cadre deux ingrédients ayant un rôle clé dans la décision et la vérification locale : la fonction d'interprétation des sorties, et l'identification des noeuds du réseau. Nous isolons également dans cette thèse l'aspect de la localité en l'étudiant sous le prisme du modèle "non-signalling", qui bien que n'étant pas un modèle réaliste, offre des possibilités théoriques intéressantes, notamment sur la dérivation de bornes inférieures pour le calcul distribué quantique, sans avoir à manipuler les objets de cette théorie. Finalement, en nous plaçant à la limite extrême des contraintes de localité, nous considérons la classe particulière de jeux à deux joueurs en l'absence de communication, et examinons les limites du calcul distribué quantique pour cette classe de jeux.