Reference number : GC-2017-Q1-02003, amendment number : , agreement type : G, recipient legal name : Friedman, Joel (The University of British Columbia), recipient country : CA, recipient province : nan, recipient city : British Columbia|Colombie-Britannique, recipient postal code : nan, program name english : Discovery Grants Program - Individual, program name french : Programme de subventions à la découverte - individuelles, program purpose english : 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 purpose french : 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., agreement title english : Expanders, Sheaves on Graphs, and Applications, agreement title french : Expanders, Sheaves on Graphs, and Applications, agreement number : RGPIN, agreement value : 100000.0, agreement start date : 2017-05-10, agreement end date : nan, description english : nan, description french : nan, expected results english : nan, expected results french : nan, additional information english : Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023), additional information french : Subvention ou bourse octroyée s'appliquant à plus d'un exercice financier. (2017-2018 à 2022-2023), owner organization : nserc-crsng, owner organization title : Natural Sciences and Engineering Research Council of Canada | Conseil de recherches en sciences naturelles et en génie du Canada