Spectra, Algorithms and Random Walks on Random Networks
Spectre, algorithmes et marches aléatoires dans des réseaux aléatoires
13 – 17 January 2020
|
Scientific Committee
Comité scientifique Mark Rudelson (University of Michigan) |
Organizing Committee
Comité d’organisation Louigi Addario-Berry (McGill University) |
|
The theory of random graphs is a field in evolution. Since its beginning at the end of the fifties until the present day, these random discrete structures have been increasingly used in mathematics and, more broadly, in computer science, in physics, biology and the social sciences. They are commonly employed to model large complex networks and disordered lattices. They are also used in the design of algorithms and to prove the existence of sophisticated combinatorial structures. Their popularity comes from the fact that they have proved to be both versatile and propitious to analytical study.
This activity has generated a number of exciting new mathematical questions. These questions are offundamental importance to understanding the subtle interplay between the geometry of the graph and the processes defined on it. A vast research effort is notably devoted to the rigorous understanding of the properties of spectra, random walks and spectral algorithms defined on random graphs. These three objects are closely related and they are at the core of both theoretical and more applied issues. They range from wave propagation in disordered media to community detection in social networks. |
La théorie des graphes aléatoires est un domaine en évolution. Depuis ses débuts à la fin des années cinquante jusqu’à nos jours, ces structures aléatoires discrètes ont été de plus en plus utilisées en mathématiques et, plus largement, en informatique, physique, biologie et dans les sciences sociales. Ils sont communément utilisés pour modéliser des grands réseaux complexes ou des cristaux impurs. Ils servent également à la conception d’algorithmes et à prouver l’existence de structures combinatoires sophistiquées. Leur popularité provient certainement du fait qu’ils sont à la fois polyvalents et propices à l’analyse mathématique.
Cette activité a généré de nombreuses nouvelles questions mathématiques très motivantes. Ces questions sont d’une importance fondamentale pour comprendre les connections subtiles entre la géométrie d’un graphe et les propriétés des processus définis dessus. Dans ce vaste programme, un effort de recherche particulièrement important est consacré à la compréhension du spectre, des marches aléatoires et des algorithmes spectraux définis sur des graphes aléatoires. Ces trois objets sont intimement reliés et ils sont au centre d’enjeux théoriques et applicatifs de première importance, Ils vont de la propagation des ondes dans les milieux désordonnés à la détection de communautés dans les réseaux sociaux. |
Richard Aoun (American University of Beirut) Law of large numbers for the spectral radius of random matrix products
Octavio Arizmendi (CIMAT) Energy of a graph
Fanny Augeri (Weizmann Institute of Science) Large deviation upper tail of cycle counts in Erdös-Renyi graphs
Luca Avena (University of Leiden) Mixing time for RW on dynamic configuration model
Ágnes Backhausz (Eötvös Loránd University And Alfréd Rényi Institute of Mathematics) Action convergence operators and applications
Jess Banks (University of California-Berkeley) Vector Colorings of Irregular Graphs, and the Maximal Entropy Non-backtracking Random Walk
Anirban Basak (Tata Institute of Fundamental Research) Upper tail large deviations of subgraph counts in sparse random graphs
Nicholas Cook (Stanford University)
Simon Coste (INRIA Paris) Weighted Erdös-Renyi graphs
Laura Eslava (National Autonomous University of Mexico) Branching processes with merges and locality of hypercube’s critical percolation
Joel Friedman (University of British Columbia) Relative expansion and trace methods
Antti Knowles (University of Geneva) Spectral analysis of critical Erdös-Rényi graphs
Laurent Ménard, (Université Paris Nanterre) The depth-first exploration of a supercritical configuration model
Léo Miolane (New York University) Phase transitions in generalized linear models
Dieter Mitsche (CNRS, Université Jean-Monnet-Saint-Étienne) The contact process on random hyperbolic graphs: metastability and critical exponent
Roberto Oliveira (IMPA) Estimating graph parameters with random walks
Matteo Quattropani (University Roma Tre. Trichotomy phenomena in the mixing of sparse digraphs
Kavita Ramanan (Brown University) Asymptotics of r-to-p norms for random matrices
Mostafa Sabri (CNRS, Université Paris-Sud) On the empirical spectral measure of some directed graphs arising in Baker maps
Arnab Sen (University of Minnesota) Majority dynamics on the infinite 3-regular tree
Nikhil Srivastava (University of California-Berkeley) A matrix expander Chernoff bound
Alexandre Stauffer (University Roma Tre) Mixing time of random walk on dynamical percolation
Ke Wang (Hong Kong University of Science and Technology) Random perturbation of low-rank matrices
Ofer Zeitouni (Weizmann Institute of Science) On determinants of random matrices
 |
 Projet SAMARA
|