Antonin Callard

(LIP, ENS Lyon)

En complexité de communication, les langages réguliers sont exactement les langages qui peuvent être calculés par des protocoles de calcul distribués impliquant deux personnes, Alice et Bob, en échangeant seulement une quantité bornée d'information. Dans cet exposé, j'utilise la complexité de communication pour quantifier l'information des espaces de pavages dits « sofiques », qui généralisent les langages réguliers de mots finis à des ensembles de coloriages infinis du plan discret Z². Motivé par la compréhension de l'expressivité calculatoire/informationnelle des espaces de pavages sofiques, je considérerai un exemple d'espace de pavages inspiré par le problème de communication NEQ. Je prouverai en particulier une version faible de sa soficité, en implémentant un protocole de calcul probabiliste pour NEQ dans les pavages d'un espace sofique. (Travaux communs avec Pascal Vanier)