Dans le cadre de systèmes distribués, de nombreux protocoles sont mis en place de manière décentralisée pour calculer des informations importantes sur le réseau.
Les nœuds du réseau doivent ainsi prendre une décision en ayant seulement une vision locale du système.
Le calcul de colorations, d'ensembles indépendants ou d'ensembles dominants sont par exemple des sous-routines importantes.

Depuis des décennies, de nombreuses bornes inférieures théoriques ont été établies sur la distance à laquelle les agents ont besoin d'extraire de l'information (la ``localité'' du problème).
Or en pratique, certaines heuristiques fonctionnement particulièrement bien malgré leur piètre efficacité théorique.
Une des raisons qui peut expliquer ce comportement est la structure des réseaux.
En effet, les graphes sous-jacents sont souvent extrêmement structurés et non arbitraires.
Le but de la thèse sera d'étudier théoriquement à quel point, dans les graphes structurés, la localité de certains problèmes peut être améliorée.

Bien que la modélisation fasse directement appel à des graphes, peu de notions de théorie des graphes ont vraiment été utilisées dans ce domaine. La thèse portera sur plusieurs domaines à l'intersection entre calcul distribué et théorie des graphes. La thèse portera tout particulièrement sur la certification locale et des algorithmes efficaces dans les modèles LOCAL et CONGEST pour les graphes structurés.