IMB > Recherche > Séminaires

Séminaire Images Optimisation et Probabilités

Responsables : Arthur Leclaire et Camille Male

  • Le 24 janvier 2019 à 11:00
  • Salle de Conférences
    Pascal Maillard (CRM & Paris Sud)
    The algorithmic hardness threshold for continuous random energy models
    I will report on recent work with Louigi Addario-Berry on algorithmic hardness for finding low-energy states in the continuous random energy model of Bovier and Kurkova. This model can be regarded as a toy model for strongly correlated random energy landscapes such as the Sherrington--Kirkpatrick model. We exhibit a precise and explicit hardness threshold: finding states of energy above the threshold can be done in linear time, while below the threshold this takes exponential time for any algorithm with high probability. I further discuss what insights this yields for understanding algorithmic hardness thresholds for random instances of combinatorial optimization problems.
  • Le 31 janvier 2019 à 11:00
  • Salle de Conférences
    Sandrine Dallaporta (CMLA, ENS Paris-Saclay)
    Statistiques linéaires des valeurs propres pour le modèle de Wigner déformé
    Dans cet exposé, on considère une matrice de Wigner déformée par une perturbation diagonale déterministe, notée Xn. Le comportement de la mesure spectrale empirique est connu et on s'intéresse aux fluctuations des statistiques linéaires des valeurs propres, c’est-à-dire aux quantités de la forme Tr f(Xn), où f est une fonction test. On présentera des résultats récents de Ji et Lee, établissant les fluctuations lorsque la fonction f est analytique, ainsi qu’un travail en collaboration avec Maxime Février (Université Paris-Sud).
  • Le 7 février 2019 à 11:00
  • Salle de Conférences

  • Le 14 février 2019 à 11:00
  • Salle de Conférences
    Anna Ben-Hamou (LPSM, Paris 6)
    Temps de mélange de marches aléatoires sur des graphes aléatoires à communautés
    Le temps de mélange d’une marche aléatoire sur un graphe connexe fini est intimement lié à l’existence de goulots d’étranglement dans le graphe: intuitivement, plus il est difficile pour la marche de passer d’une région du graphe à une autre, plus le mélange est lent. De plus, la présence de goulots d’étranglement étroits empêche souvent le phénomène de cutoff, qui décrit une convergence abrupte à l’équilibre. Dans cet exposé, nous nous intéresserons au comportement de mélange de la marche aléatoire sans rebroussement (« non-backtracking ») sur des graphes aléatoires à degrés prescrits et avec une structure en deux communautés. De tels graphes possèdent un goulot d’étranglement dont l’étroitesse peut être mesurée par la fraction des arêtes qui vont d’une communauté à l’autre. Sous certaines conditions de degrés, nous montrerons que si cette fraction décroit moins vite que 1/log(N) (où N est la taille du graphe), alors la marche présente le cutoff, et la distance à l’équilibre peut être décrite très précisément. Inversement, si cette fraction décroit plus vite que 1/log(N), alors il n’y a pas cutoff.
  • Le 7 mars 2019 à 11:00
  • Salle de Conférences
    Pierre Perruchaud (IRMAR, Rennes 1)

  • Le 14 mars 2019 à 11:00
  • Salle de Conférences

  • Le 21 mars 2019 à 11:00
  • Salle de Conférences

  • Le 28 mars 2019 à 11:00
  • Salle de Conférences

  • Le 4 avril 2019 à 11:00
  • Salle de Conférences

  • Le 11 avril 2019 à 11:00
  • Salle de Conférences

  • Le 2 mai 2019 à 11:00
  • Salle de Conférences

  • Le 9 mai 2019 à 11:00
  • Salle de Conférences

  • Le 16 mai 2019 à 11:00
  • Salle de Conférences

  • Le 23 mai 2019 à 11:00
  • Salle de Conférences

  • Le 6 juin 2019 à 11:00
  • Salle de Conférences

  • Le 13 juin 2019 à 11:00
  • Salle de Conférences

    Les séminaires à partir de 2016