Grant: Discovery Grants Program - Individual
University of Waterloo
$53,000.00
Random structures and algorithms
EF 2011-12
Résumé
Random structures are useful for designing and analysing computer algorithms which solve modern-day problems. They can also be useful for understanding properties of large complex systems such as the link structure of peer-to-peer networks. This proposal aims to continue the study of some relatively new techniques for proving properties of random structures, as well as developing some very new techniques. It will advance the field of combinatorial mathematics in areas of fundamental importance, and aims also to include application-oriented topics arising from computer science, real-world networks, and other contemporary fields of science.
Some of the problems to be tackled involve load balancing. These problems arise when requests are sent to a set of processors (or storage disks), and one wants to allocate the requests such that no processor is assigned many more than its fair share. The aim is to show that certain very fast algorithms for performing the allocation often succeed in balancing the load quite evenly. Other problems relate to peer-to-peer networks. The aim there is to study the theoretical properties of the networks used in practice, concentrating on those properties that are desirable from performance considerations. Yet other problems involve further properties of random graphs, an abstraction of the above problems whose study has yielded the sort of techniques that are to be used in this work.
The overall impact of the proposal should be the solution of a number of problems of high contemporary interest, and a significant improvement of the understanding of the field.
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
261956-2007
Name nom
Wormald, Nicholas
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
2011
Competition year année de concours
2007
Award amount
53000
Program id
RGPIN
Program nane en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
5
Nb partie
5
Application title
Random structures and algorithms
Keyword
NSERC
Application summary
Random structures are useful for designing and analysing computer algorithms which solve modern-day problems. They can also be useful for understanding properties of large complex systems such as the link structure of peer-to-peer networks. This proposal aims to continue the study of some relatively new techniques for proving properties of random structures, as well as developing some very new techniques. It will advance the field of combinatorial mathematics in areas of fundamental importance, and aims also to include application-oriented topics arising from computer science, real-world networks, and other contemporary fields of science.
Some of the problems to be tackled involve load balancing. These problems arise when requests are sent to a set of processors (or storage disks), and one wants to allocate the requests such that no processor is assigned many more than its fair share. The aim is to show that certain very fast algorithms for performing the allocation often succeed in balancing the load quite evenly. Other problems relate to peer-to-peer networks. The aim there is to study the theoretical properties of the networks used in practice, concentrating on those properties that are desirable from performance considerations. Yet other problems involve further properties of random graphs, an abstraction of the above problems whose study has yielded the sort of techniques that are to be used in this work.
The overall impact of the proposal should be the solution of a number of problems of high contemporary interest, and a significant improvement of the understanding of the field.