AF: Small: Collaborative Research: Matrix Signings and Algorithms for Expanders and Combinatorial Nullstellensatz

这个项目将研究图相关矩阵的谱特性及其符号，这已经成为计算机科学的基本工具。这些矩阵的频谱在许多领域产生了巨大的影响，包括机器学习，数据挖掘，网络搜索和排名，博弈论，科学计算和计算机视觉，并影响了一些算法创新。该项目将产生重大的技术和教育影响。该项目固有的数学和算法性质以及大量潜在的实际应用将汇集来自数学和网络设计等不同领域的研究人员。研究人员将组织一个关于谱图理论的研讨会，汇集这些领域的专家。该项目将支持研究生，他们将在算法的设计和分析方面接受指导和广泛的培训。研究人员还将通过针对STEM学科中代表性不足的群体的教育活动，特别努力促进多样性。在该项目中，研究人员将设计有效的算法，用于构建各种组合结构，这些结构通过适当的矩阵符号来保证存在。要研究的组合结构包括扩展图和代数方法的其他几个应用。值得注意的是，有效构造扩展图的算法问题是谱图理论的核心。这个项目将开发一个全面的理解的内在困难，以及提出算法，有效地构建扩展图通过签署邻接矩阵。组合零空间是一个强大的代数工具，经常用来证明某些组合结构的存在性。然而，其证明的非构造性一直是有效找到这些结构的障碍。基于代数方法的潜在证明在建设性的前沿（与基于概率方法的那些不同）抵制了进展。在这个项目中，研究人员将沿着这一方向取得突破，为组合零辐射的有限应用获得有效的建设性证明。这个奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

This project will investigate spectral properties of graph-related matrices and their signings, which have become fundamental tools in computer science. The spectra of such matrices have had a tremendous impact in numerous areas including machine learning, data mining, web search and ranking, game theory, scientific computing, and computer vision and have influenced several algorithmic innovations. The project will have significant technical as well as educational impacts. The inherent mathematical and algorithmic nature of the project together with the plethora of potential practical applications will bring together researchers from varied areas such as mathematics and network design. The investigators will organize a workshop on Spectral Graph Theory to bring together experts in these areas. The project will support graduate students who will receive mentoring and extensive training in the design and analysis of algorithms. The investigators will also direct special efforts towards fostering diversity through educational activities targeting under-represented groups in STEM disciplines.In this project, the investigators will design efficient algorithms for constructing various combinatorial structures that are guaranteed to exist through suitable signings of matrices. The combinatorial structures to be studied include expander graphs and several other applications of the algebraic method. Notably, the algorithmic problem of efficiently constructing of expander graphs is at the core of spectral graph theory. This project will develop a comprehensive understanding of the inherent difficulties, as well as propose algorithms for efficiently constructing expander graphs via signed adjacency matrices. Combinatorial Nullstellensatz is a powerful algebraic tool often used to show the existence of certain combinatorial structures. However, the non-constructive nature of its proof has been a barrier towards finding these structures efficiently. Existential proofs based on the algebraic method have resisted progress on the constructive front (unlike those based on probabilistic method). In this project, the investigators will break ground along this direction by obtaining efficient constructive proofs for restricted applications of Combinatorial Nullstellensatz.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.