- Nicolas Gauvrit (EPHE) : Complexité algorithmique appliquée à la cognition
Résumé : La complexité algorithmique peut aujourd’hui être approchée de manière plus fiable et plus précise grâce à la création récente d’une méthode d’approximation fondée sur des calculs massifs. Les potentialités de cette méthode, que des psychologues comme Nick Chater et des mathématiciens comme Paul Vitányi avaient déjà soupçonnées il y a 20 ans, prennent une nouvelle dimension et se développent en sciences humaines dans des domaines étonnants de diversité. Nous verrons comment, associée à l’approche « bayésienne » en psychologie, elle permet d’étudier notamment la perception du hasard, la mémoire, le raisonnement, ou l’évolution des langues.
- Dieter Mitsche (Univ. Nice Sophia Antipolis) : Sur le trou spectral des graphes aléatoires hyperboliques
Résumé : Le modèle des graphes aléatoires hyperboliques a été introduit comme un modèle prometteur pour les réseaux complexes. Nous considérons le modèle de Krioukov et al. et nous calculons le trou spectral de la Laplacienne de ce modèle. Plus précisément, nous montrons que $lambda_2$ d’un tel graphe est $Omega(n^{-(2alpha-1)}/polylog(n))$, où $n$ est le nombre de noeuds et $ 1/2 < alpha < 1$ est un paramètre du modèle. Nous concluons aussi que la borne supérieure de $lambda_2$ obtenue par l’inégalité de Cheeger est presque atteinte. Nous caractérisons aussi les ensembles des noeuds pour lesquelles cette borne est atteinte. (Travail en collaboration avec Marcos Kiwi)
