Grant: Discovery Grants Program - Individual
University of British Columbia
$27,000.00
Expanders and related topics
EF 2009-10
Résumé
When there is a lot of traffic on a communication network, the network may develop "hot spots," i.e. links (edges) where there is a "large" number of packets (messages, phone calls, etc.) which want to use that link. A type of network or graph where this does not happen (given a good routing strategy) is a type of graph known as an "expander."
Expanders have a large number of applications to computer science theory, including to randomness, routing, and other areas. The problem of building them (i.e. giving explicit constructions) has drawn a lot of attention in the computer science theory and mathematics communities. There has been significant progress towards explicitly constructing expanders, although a number of compelling problems remain open; much of this progress uses an important connection between expanders and the linear algebra of the graph's adjacency matrix, namely its eigenvalues.
This project aims to further study expanders and their relationships to the linear (and non-linear) algebra of the graph's adjacency matrix.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
156255-2007
Name nom
Friedman, Joel
Department département
Computer Science
Organization id
2
Institution établissement
University of British Columbia
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2009
Competition year année de concours
2007
Award amount
27000
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
2712
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Theory of computation
Research subject fr
Théorie de calcul
Partie
3
Nb partie
5
Application title
Expanders and related topics
Keyword
NA
Application summary
When there is a lot of traffic on a communication network, the network may develop "hot spots," i.e. links (edges) where there is a "large" number of packets (messages, phone calls, etc.) which want to use that link. A type of network or graph where this does not happen (given a good routing strategy) is a type of graph known as an "expander."
Expanders have a large number of applications to computer science theory, including to randomness, routing, and other areas. The problem of building them (i.e. giving explicit constructions) has drawn a lot of attention in the computer science theory and mathematics communities. There has been significant progress towards explicitly constructing expanders, although a number of compelling problems remain open; much of this progress uses an important connection between expanders and the linear algebra of the graph's adjacency matrix, namely its eigenvalues.
This project aims to further study expanders and their relationships to the linear (and non-linear) algebra of the graph's adjacency matrix.