Expanders, Sheaves on Graphs, and Applications

理论计算机科学已经产生了许多重要的问题*，这些问题可以用被称为*线性代数的数学子领域的技术来解决。我们的建议是将*线性代数中的一些相关技术应用到“图论”中，来研究这样的问题。线性代数与这类问题的*联系是众所周知的。我们的建议*旨在加强线性代数中已知的技术，以期*它们的应用，以解决理论计算机科学中的问题。*这种技术也可以用来解决一些*数学领域的问题；事实上，我们感兴趣的计算机科学中的问题*与一些数学和物理领域有关。在另一个*方向，这些相关领域的研究成果，我们有时可以*借用，以增强我们对线性代数和计算机科学感兴趣的部分的知识。*我们提出的研究是由两个理论计算机科学领域*一个被称为“扩展图”和另一个被称为“复杂性理论”。我们所研究的线性代数的*领域是在“图论”中产生的某些矩阵的“特征值”和“谱*理论”，以及与之相关的“层理论”的概念。虽然层理论通常被视为*代数拓扑学的领域，但我们对层理论的兴趣在于“向量*空间的层”，这是一种通过*图的结构来增强的线性代数。*我们对“扩展图”的研究集中在“相对扩展”上，这是从较小的网络构建较大网络的一种*方法，在这种方式下，人们可以*理解大网络的扩展是根据较小的网络以及*大网络位于较小网络之上的方式。最近，已经有*许多结果和从较小的网络构造新的网络。相对扩展的*基础始于2003年我们的一篇论文，灵感来自Alexander Grothendieck在拓扑学和代数几何方面的工作。*我们对层理论的研究使我们能够比较位于同一图上的线性代数中的结构*；这种类型的层理论还处于初级阶段。我们*是在复杂性理论的驱使下开始研究这个理论的，但我们用它来*解决了1950年S关于群论的汉娜·诺伊曼猜想。这一理论的灵感来自于Grothendieck和他的同事们的工作。因此，我们的项目利用了计算机科学和数学领域之间富有成效的联系。

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.