Grant: Discovery Grants Program - Individual
University of British Columbia
$20,000.00
Expanders, Sheaves on Graphs, and Applications
FY 2020-21
Summary
Theoretical computer science has given rise to a number of important problems
that can be attacked with techniques of the subfield of mathematics known as
linear algebra. Our proposal is to use a number of related techniques in
linear algebra applied to "graph theory", to study such problems. The
connection of linear algebra to such problems is well known. Our proposal
seeks to strengthen the known techniques in linear algebra, with a view towards
their applications, to solve problems in theoretical computer science.
Such techniques can be used also to solve problems in a number of fields of
mathematics; indeed, the problems in computer science of interest to us are
related to a number of areas of mathematics and physics. In the other
direction, these related areas have research results which we can sometimes
borrow to enhance our knowledge of the parts of linear algebra and computer
science of interest to us.
Our proposed research is motived by two areas of theoretical computer science,
one known as "expander graphs", another known as "complexity theory". The
areas of linear algebra that we work with are the "eigenvalues" and "spectral
theory" of certain matrices arising in to "graph theory", and the related
notion of "sheaf theory". While sheaf theory is often viewed as a field of
algebraic topology, our interest in sheaf theory is in "sheaves of vector
spaces," which is a type of linear algebra that is enhanced by the structure of
a graph.
Our research in "expander graphs" focuses on "relative expansion," which is a
way of building larger networks from smaller ones, in a way where one can
understand expansion of the large network in terms of the smaller network and
the way the large network lies "over" the smaller one. Recently there has been
a lot of results and constructions of new networks from smaller ones. The
foundations of relative expansion began in a paper of ours from 2003, motivated
by work of Alexander Grothendieck in topology and algebraic geometry.
Our research in sheaf theory allows us to compare structures in linear algebra
that lie over the same graph; this type of sheaf theory is in its infancy. We
began to study this theory motivated by complexity theory, but have used it to
solve the Hanna Neumann Conjecture of the 1950's regarding group theory. This
sheaf theory was inspired by work of Grothendieck and his colleagues.
Hence our project exploits the fruitful connection between areas of computer
science and mathematics.
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2017-04463
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
2020
Competition year année de concours
2017
Award amount
20000
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
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
Installment
inst:4-5
Partie
2
Nb partie
5
Application title
Expanders, Sheaves on Graphs, and Applications
Keyword
NSERC
Application summary
Theoretical computer science has given rise to a number of important problems
that can be attacked with techniques of the subfield of mathematics known as
linear algebra. Our proposal is to use a number of related techniques in
linear algebra applied to "graph theory", to study such problems. The
connection of linear algebra to such problems is well known. Our proposal
seeks to strengthen the known techniques in linear algebra, with a view towards
their applications, to solve problems in theoretical computer science.
Such techniques can be used also to solve problems in a number of fields of
mathematics; indeed, the problems in computer science of interest to us are
related to a number of areas of mathematics and physics. In the other
direction, these related areas have research results which we can sometimes
borrow to enhance our knowledge of the parts of linear algebra and computer
science of interest to us.
Our proposed research is motived by two areas of theoretical computer science,
one known as "expander graphs", another known as "complexity theory". The
areas of linear algebra that we work with are the "eigenvalues" and "spectral
theory" of certain matrices arising in to "graph theory", and the related
notion of "sheaf theory". While sheaf theory is often viewed as a field of
algebraic topology, our interest in sheaf theory is in "sheaves of vector
spaces," which is a type of linear algebra that is enhanced by the structure of
a graph.
Our research in "expander graphs" focuses on "relative expansion," which is a
way of building larger networks from smaller ones, in a way where one can
understand expansion of the large network in terms of the smaller network and
the way the large network lies "over" the smaller one. Recently there has been
a lot of results and constructions of new networks from smaller ones. The
foundations of relative expansion began in a paper of ours from 2003, motivated
by work of Alexander Grothendieck in topology and algebraic geometry.
Our research in sheaf theory allows us to compare structures in linear algebra
that lie over the same graph; this type of sheaf theory is in its infancy. We
began to study this theory motivated by complexity theory, but have used it to
solve the Hanna Neumann Conjecture of the 1950's regarding group theory. This
sheaf theory was inspired by work of Grothendieck and his colleagues.
Hence our project exploits the fruitful connection between areas of computer
science and mathematics.