Expanders, Sheaves on Graphs, and Applications

理论计算机科学引起了许多重要的问题

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.