Grant: Discovery Grants Program - Individual
McGill University
$96,000.00
Structural and algorithmic properties of random networks
EF 2023-24
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
2023
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
2712
Research subject group en
Information technology
Research subject group fr
Theory of computation
Research subject en
Technologie de l'information
Research subject fr
Théorie de calcul
Application title
Structural and algorithmic properties of random networks
Keyword
Analysis of algorithms; Branching processes; Detecting extremes in random fields; Discrete probability; Discrete stochastic processes; Phase transitions; Planar maps; Random graphs; Random networks; Random trees
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.