La certification locale est un modèle de calcul distribué, dans lequel les sommets d'un réseau ont pour but de décider collectivement si le réseau satisfait ou non une propriété donnée. À l'origine, la certification locale était motivée par les algorithmes auto-stabilisants (qui sont un autre modèle d'algorithmes distribués), pour vérifier efficacement la validité d'une solution à un problème dans un environnement sujets à des fautes. Aujourd'hui, la certification locale est étudiée comme un sujet à part entière, indépendamment des algorithmes auto-stabilisants.
En certification locale, pour décider si une propriété donnée est satisfaite ou non par le réseau, chaque sommet reçoit une information, appelée un certificat, qu'il peut communiquer à travers le réseau, mais seulement avec ses voisins (c'est pour cela que ce mécanisme est qualifié de local). Ensuite, à partir de son propre certificat et de ceux de ses voisins, chaque sommet prend sa propre décision, sous la forme d'une réponse binaire (acceptation ou rejet). Un algorithme de certification est dit correct si les réseaux satisfaisant la propriété sont exactement les réseaux pour lesquels les sommets peuvent tous accepter simultanément avec une certaine assignation de certificats.
La taille des certificats est habituellement exprimée en fonction du nombre de sommets dans le réseau. Le but est, pour une propriété donnée, d'optimiser cette taille afin de la rendre la plus petite possible. Cette taille des certificats peut aussi être vue comme une mesure de la localité de la propriété, et dans cette thèse, on l'appellera la complexité locale de la propriété. Un résultat fondamental établit que la complexité locale de toute propriété est au plus quadratique en le nombre de sommets. Cependant, beaucoup de propriétés peuvent être certifiées de façon beaucoup plus efficace : pour un certain nombre d'entre elles, des certificats de taille logarithmique sont suffisants.
Dans cette thèse, nous étudions plusieurs aspects de la complexité locale. Notre but est d'avoir une meilleure compréhension de chacun des différents régimes de complexité locale (constant, poly-logarithmique ou polynomial). Après avoir présenté les définitions principales et les outils habituels en certification, cette thèse est organisée en cinq chapitres techniques. Les deux premiers concernent l'étude des propriétés ayant une complexité locale très faible (entre constante et logarithmique), tandis que les trois derniers chapitres explorent les propriétés ayant une complexité locale polynomiale. Nous prouvons des bornes optimales sur la complexité locale d'un grand nombre de propriétés, établissons des théorèmes caractérisant les complexités locales pouvant exister ou non dans certaines classes de graphes restreintes, et développons de nouvelles techniques pour prouver des bornes supérieures et inférieures.