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

University Of Colorado At Boulder, Boulder CO

Investigators

Abstract

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.