Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of British Columbia

$28,000.00

Expanders and Related Topics

EF 2015-16

Résumé
Expander graphs is a field that essentially seeks to find communication networks that are ""well interconnected."" Two networks with the same number of nodes and links can still have very different ""interconnectivity"" properties; for example, if some half of the nodes of a network have very few links to the other half, communication between the two halves can be problematic. Roughly speaking, an expander is a network in which such connectivity issues do not occur. The expansion properties of a graph can be studied via the eigenvalues of the graph's adjacency matrix. This approach to connectivity or ""geometric"" properties via linear algebra has been very successful. Furthermore, other combinatorial properties of structures used in theoretical computer science and mathematics can be understood via associated linear algebra and matrices, especially their eigenvalue structure. One theme of this project is to try to use diverse mathematical tools--tools not usually associated with expanding graphs and theoretical computer science--to gain new insight into expanders. Thus the researchers involved with this project--especially students and postdocs--often must spend substantial amounts of time learning new areas of mathematics, even if they are already familiar with the basics of expanders. This means that our project has a high ""start up"" cost in terms of required background; we believe this high cost is justified by the achievements we have made. These achievements include proving the Alon Conjecture, that gives the best bounds on random expanders and the, in many cases, the best bound on any expander in a certain class. Another achievement has been to prove the well known Hanna Neumann Conjecture, a conjecture of the 1950's in a field of mathematics; we proved this with techniques we designed to study complexity theory. This project hence demonstrates a cross fertilization between theoretical computer science and diverse mathematical fields.
Programme
Discovery Grants Program - Individual
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
156255-2012
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
2015
Competition year année de concours
2012
Award amount
28000
Program id
RGPIN
Program name 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
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
Technologie de l'information
Research subject en
Theory of computation
Research subject fr
Théorie de calcul
Partie
4
Nb partie
5
Application title
Expanders and Related Topics
Keyword
NSERC
Application summary
Expander graphs is a field that essentially seeks to find communication networks that are ""well interconnected."" Two networks with the same number of nodes and links can still have very different ""interconnectivity"" properties; for example, if some half of the nodes of a network have very few links to the other half, communication between the two halves can be problematic. Roughly speaking, an expander is a network in which such connectivity issues do not occur. The expansion properties of a graph can be studied via the eigenvalues of the graph's adjacency matrix. This approach to connectivity or ""geometric"" properties via linear algebra has been very successful. Furthermore, other combinatorial properties of structures used in theoretical computer science and mathematics can be understood via associated linear algebra and matrices, especially their eigenvalue structure. One theme of this project is to try to use diverse mathematical tools--tools not usually associated with expanding graphs and theoretical computer science--to gain new insight into expanders. Thus the researchers involved with this project--especially students and postdocs--often must spend substantial amounts of time learning new areas of mathematics, even if they are already familiar with the basics of expanders. This means that our project has a high ""start up"" cost in terms of required background; we believe this high cost is justified by the achievements we have made. These achievements include proving the Alon Conjecture, that gives the best bounds on random expanders and the, in many cases, the best bound on any expander in a certain class. Another achievement has been to prove the well known Hanna Neumann Conjecture, a conjecture of the 1950's in a field of mathematics; we proved this with techniques we designed to study complexity theory. This project hence demonstrates a cross fertilization between theoretical computer science and diverse mathematical fields.