Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

McGill University

$96,000.00

Structural and algorithmic properties of random networks

EF 2024-25

Résumé
My work focusses principally on the structural and algorithmic properties of large random structures (e.g. random graphs, random trees, random maps). Here are some of my main research themes for the coming years. 1) Detecting optima and extremes in huge systems via local search processes For many paradigmatic, computationally hard optimization problems, there are efficient algorithms which find nearly optimal solutions for "typical" instances; for others there are information-theoretic barriers which allow for proofs that no such algorithms exist. I plan to study such statistical thresholds for algorithmic detection of extremes and optima, building on my work on the threshold for efficient detection in the continuous random energy model. 2) Network archaeology Here is a paradigmatic question from this exciting young field: suppose at some time t we observe a computer virus which has randomly spread through a network. If we know the network structure, and the set of sites which have been exposed to the virus (but not when), can we determine the likely time-zero source of the virus? If so, how efficiently? I aim to extend existing research (which is mostly restricted to the setting of trees) to more more flexible and realistic models. 3) Properties of large random graphs Since their introduction in the seminal work of Erdös and Rényi in 1960, thousands of research papers about random graphs have been published; but some surprisingly basic questions remain unanswered. I intend to develop the theory in several ways. For instance: to characterize when connectivity occurs with high probability in random graphs with given degrees; to describe the full structure of critical random directed graphs; to build the theory of tree-weighted graphs; and to generalize of the theory of branching processes to allow for approximating networks with short cycles which are only treelike on larger scales. 4) Numerical PDEs and convergence of random processes A large part of probability theory involves proving convergence of discrete systems to continuous ones. This is also the case in the area of numerical approximation of differential equations (PDEs). The idea that this provides a useful connection between probability and numerical PDEs is not well-developed and is a new excitement of mine. I intend to develop a toolkit of numerical PDE methods which can be applied in probabilistic settings, and conversely, to export ideas from discrete probability/ analysis of algorithms to provide tools for proving convergence of numerical approximations of PDEs. 5) Canonical embeddings of random maps I intend to study algorithmic embedding rules for planar graphs (Schnyder woods, squaring embeddings), and the statistical properties of the resulting embeddings of large random maps. The goal of this line of research is to understand the asymptotic conformal structure of various large random map ensembles.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2023-03968
Name nom
Addario-Berry, Louigi
Department département
Mathematics and Statistics
Organization id
61
Institution établissement
McGill University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2023
Award amount
96000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
3007
Research subject group en
Statistics and probability
Research subject group fr
Statistique et probabilité
Research subject en
Stochastic processes
Research subject fr
Processus stochastiques
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Structural and algorithmic properties of random networks
Keywords
discrete probability; random trees; analysis of algorithms; branching processes; detecting extremes in random fields; phase transitions; random graphs; planar maps; random networks; discrete stochastic processes
Application summary
My work focusses principally on the structural and algorithmic properties of large random structures (e.g. random graphs, random trees, random maps). Here are some of my main research themes for the coming years. 1) Detecting optima and extremes in huge systems via local search processes For many paradigmatic, computationally hard optimization problems, there are efficient algorithms which find nearly optimal solutions for "typical" instances; for others there are information-theoretic barriers which allow for proofs that no such algorithms exist. I plan to study such statistical thresholds for algorithmic detection of extremes and optima, building on my work on the threshold for efficient detection in the continuous random energy model. 2) Network archaeology Here is a paradigmatic question from this exciting young field: suppose at some time t we observe a computer virus which has randomly spread through a network. If we know the network structure, and the set of sites which have been exposed to the virus (but not when), can we determine the likely time-zero source of the virus? If so, how efficiently? I aim to extend existing research (which is mostly restricted to the setting of trees) to more more flexible and realistic models. 3) Properties of large random graphs Since their introduction in the seminal work of Erdös and Rényi in 1960, thousands of research papers about random graphs have been published; but some surprisingly basic questions remain unanswered. I intend to develop the theory in several ways. For instance: to characterize when connectivity occurs with high probability in random graphs with given degrees; to describe the full structure of critical random directed graphs; to build the theory of tree-weighted graphs; and to generalize of the theory of branching processes to allow for approximating networks with short cycles which are only treelike on larger scales. 4) Numerical PDEs and convergence of random processes A large part of probability theory involves proving convergence of discrete systems to continuous ones. This is also the case in the area of numerical approximation of differential equations (PDEs). The idea that this provides a useful connection between probability and numerical PDEs is not well-developed and is a new excitement of mine. I intend to develop a toolkit of numerical PDE methods which can be applied in probabilistic settings, and conversely, to export ideas from discrete probability/ analysis of algorithms to provide tools for proving convergence of numerical approximations of PDEs. 5) Canonical embeddings of random maps I intend to study algorithmic embedding rules for planar graphs (Schnyder woods, squaring embeddings), and the statistical properties of the resulting embeddings of large random maps. The goal of this line of research is to understand the asymptotic conformal structure of various large random map ensembles.