Grant: Discovery Grants Program - Individual
University of Waterloo
$33,000.00
Random structures from large networks and systems
EF 2019-20
Résumé
Random structures arise in many branches of science and mathematics. Among the most influential structures that affect our daily life are large networks like the Internet and online social networks. Another example is random matrices that are used to construct modern linear codes, which are widely applied in telecommunication. These examples show that research in random structures is important and timely. ******This proposal aims to advance the study of important random structures arising from random graph theory, networks, statistical physics and information theory. The goal is to develop new tools for analysing these random structures, and to develop new theoretical results on the reliability and robustness of a broad class of random graphs that are of great relevance to real-world networks.******To approach this goal, the proposed research will focus on models of random graphs that are widely used for analysing large networks, and models of random matrices that are used in statistical analysis and modern coding theory. I will address important questions to these models. In particular, I will analyse network parameters in the proposed random graph models, and these parameters are crucial measures for the robustness of the networks. I will propose new and efficient algorithms for sampling random matrices with fixed marginal (i.e. with fixed row and column sums). Such matrices are useful for testing hypotheses in statistical analysis, and there are no efficient algorithms yet with guaranteed performance. I propose to answer theoretical questions in coding theory regarding the information rate of linear codes that are constructed by a random low-density parity-check matrix. ******This study is expected to advance knowledge in random graph theory and random matrix theory. It deals with fundamental problems in these fields that are of great interest in computer science, mathematics, coding theory, and statistical physics. This proposal aims at significantly improving the current best results in the literature, for challenging problems that have been studied by many authors. It proposes to employ new proof techniques for solving long-standing open problems. ******The proposed research has the potential to produce important economic and social benefits to Canada. It will enhance knowledge of how real-world networks such as the Internet function. This can lead to important competitive advantages for Canada. The HQP students working on this project will benefit from receiving advanced training in network analysis, an area with applications in many fields. The skills they learn from undertaking this project will place them in a top position on the job market, since companies such as Facebook, Google, Twitter, eBay and Amazon seek candidates with knowledge and techniques in network analysis.**
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2019-04173
Name nom
Gao, Pu
Department département
Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2019
Competition year année de concours
2019
Award amount
33000
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
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Installment
inst:1 - 5
Partie
1
Nb partie
5
Application title
Random structures from large networks and systems
Keyword
NSERC
Application summary
Random structures arise in many branches of science and mathematics. Among the most influential structures that affect our daily life are large networks like the Internet and online social networks. Another example is random matrices that are used to construct modern linear codes, which are widely applied in telecommunication. These examples show that research in random structures is important and timely. ******This proposal aims to advance the study of important random structures arising from random graph theory, networks, statistical physics and information theory. The goal is to develop new tools for analysing these random structures, and to develop new theoretical results on the reliability and robustness of a broad class of random graphs that are of great relevance to real-world networks.******To approach this goal, the proposed research will focus on models of random graphs that are widely used for analysing large networks, and models of random matrices that are used in statistical analysis and modern coding theory. I will address important questions to these models. In particular, I will analyse network parameters in the proposed random graph models, and these parameters are crucial measures for the robustness of the networks. I will propose new and efficient algorithms for sampling random matrices with fixed marginal (i.e. with fixed row and column sums). Such matrices are useful for testing hypotheses in statistical analysis, and there are no efficient algorithms yet with guaranteed performance. I propose to answer theoretical questions in coding theory regarding the information rate of linear codes that are constructed by a random low-density parity-check matrix. ******This study is expected to advance knowledge in random graph theory and random matrix theory. It deals with fundamental problems in these fields that are of great interest in computer science, mathematics, coding theory, and statistical physics. This proposal aims at significantly improving the current best results in the literature, for challenging problems that have been studied by many authors. It proposes to employ new proof techniques for solving long-standing open problems. ******The proposed research has the potential to produce important economic and social benefits to Canada. It will enhance knowledge of how real-world networks such as the Internet function. This can lead to important competitive advantages for Canada. The HQP students working on this project will benefit from receiving advanced training in network analysis, an area with applications in many fields. The skills they learn from undertaking this project will place them in a top position on the job market, since companies such as Facebook, Google, Twitter, eBay and Amazon seek candidates with knowledge and techniques in network analysis.**