Distributed randomized and quantum algorithms for cycle detection in networks
Maël Luce
Algorithmes randomisés et quantiques pour la détection de cycle dans les réseaux distribués Détecter la présence de sous-structures spécifiques (e.g. de cycles de longueur donnée) est un problème standard dans les réseaux d'algorithmique distribuée. Cette thèse se concentre sur la détection distribuée de cycles de longueur paire, c'est-à-dire décider si le réseau contient un cycle de longueur 2k comme sous-graphe, pour tout k\geq 2. Cette collection de problèmes (un pour chaque k) est étudiée à la fois en algorithmique distribuée randomisée et quantique, dans les variants correspondant du modèle \CONGEST. Dans le modèle randomisé, la meilleure borne inférieure connue pour décider C_{2k}-freeness dans le modèle \CONGEST est \tilde Omega(\sqrt n) rondes, et, avant notre travail, la meilleure borne supérieure générale pour le problème s'appliquant à tout k\geq 2 était \tilde O(n^{1-\nicefrac{1}{\theta(k^2)}}) rondes [Eden et al., 2022]. Un algorithme plus rapide existait cependant, mais seulement pour les petites valeurs de k, à savoir pour 2\leq k\leq 5, avec une complexité en rondes de O(n^{1-\nicefrac{1}{k}}) [Censor-Hillel et al., 2020]. Ce dernier algorithme se base sur une technique originale que nous appelons la technique \emph{Local Threshold}. Nous démontrons que la technique Local Threshold ne peut être étendue pour détecter efficacement les 2k-cycles pour k\geq 6 dans le modèle \CONGEST randomisé. Néanmoins, nous démontrons qu'elle peut tout de même être utilisée pour décider l'absence de certaines \emph{familles} de cycles de longueur paire. Par exemple, en utilisant cette technique, nous démontrons que \{C_{12},C_{14}\}-freeness peut être décidé en O(n^{1-\nicefrac{1}{7}) rondes. D'une façon similaire, la technique Local Threshold peut aussi décider \{C_{4\ell}\mid 1\leq \ell \leq k\}-freeness (resp. \{C_{4\ell+2} \mid 1\leq \ell \leq k\}-freeness) en O(n^{1-\nicefrac{1}{2k}}) (resp. O(n^{1-\nicefrac{1}{(2k+1)}})) rondes. Une des deux principales contributions de cette thèse est l'élaboration de la technique \emph{Global Threshold}, pour détecter les 2k-cycles en O(n^{1-\nicefrac{1}{k}}) rondes pour tout k\geq 2. Cette technique consiste grossièrement à fusionner toutes les sous-routines de recherche utilisée dans la technique Local Threshold en une seule recherche, pour laquelle un seuil peut être fixé pour chaque valeur de k\geq 2. La seconde contribution technique de cette thèse est la quantization de notre algorithme randomisé pour décider C_{2k}-freeness. Nous démontrons, grâce à une nouvelle technique distribuée d'amplification quantique Monte-Carlo, que pour tout k\geq 2, C_{2k}-freeness peut être décidé en \tilde O(n^{\nicefrac{1}{2}-\nicefrac{1}{2k}}) rondes. Similairement, pour tout k\geq 1, C_{2k+1}-freeness peut être décidé par un algorithme quantique s'exécutant en \tilde O(\sqrt n) rondes dans le modèle \CONGEST, améliorant ainsi quadratiquement la complexité de la détection de cycles de longueur impaire plus strictement plus grande que 3, comparé au cadre randomisé. Nous établissons également des bornes inférieures, à savoir \tilde\Omega(\sqrt{n}) pour détecter les cycles de longueur paire strictement plus grande que 3, s'alignant sur notre borne supérieure, et \tilde\Omega(n^{\nicefrac{1}{4}}) pour la détection de cycle de longueur paire.
•Dec 17, 2024•0 citations