The distribution of k-tuples of reduced residues

En 1940, Paul Erdős énonça une conjecture sur la distribution des classes inversibles modulo un entier. La présente thèse étudie la distribution des k-uplets de classes inversibles propose une preuve de la conjecture d'Erdős étendue au cas des k-uplets.

Complexité de la communication sur un canal avec délai

Nous introduisons un nouveau modèle de la communication à deux parties dans lequel nous nous intéressons au temps que prennent deux participants à effectuer une tâche à travers un canal avec délai d. Nous établissons quelques bornes supérieures et inférieures et comparons ce nouveau modèle aux modèles de communication classiques et quantiques étudiés dans la littérature. Nous montrons que la complexité de la communication d’une fonction sur un canal avec délai est bornée supérieurement par sa complexité de la communication modulo un facteur multiplicatif d/ lg d. Nous présentons ensuite quelques exemples de fonctions pour lesquelles une stratégie astucieuse se servant du temps mort confère un avantage sur une implémentation naïve d’un protocole de communication optimal en terme de complexité de la communication. Finalement, nous montrons qu’un canal avec délai permet de réaliser un échange de bit cryptographique, mais que, par lui-même, est insuffisant pour réaliser la primitive cryptographique de transfert équivoque.

Émergence et entropie

Thèse effectuée en cotutelle avec l’Université de Montréal et l’Université Paris 1 Panthéon-Sorbonne (IHPST)