Spectral Graph Theory or Algebraic Graph Theory, as it is also known, is the study of the relationship between the eigenvalues and eigenvectors of graphs and their combinatorial properties. The project will focus on furthering our understanding of this relationship and exploit this understanding to design new and efficient algorithms. Included in this list of algorithmic problems will be fast and reliable linear system solvers and graph partitioners. These new algorithms will in turn be used to find better and more efficient algorithms for problems in image processing, medical imaging, machine learning, and linear and non-linear optimizations. Enabling technology will include linear-work or O(m log m)-work algorithms for computing extreme eigenvalues of symmetric diagonally dominate systems. The project will uses ideas and techniques from graph theory such as graph sparsifiers, graph cuts, and Steiner trees. These graph theoretic ideas will be combined with numerical methods such as Krylov subspaces methods, interior point methods, and preconditioning methods to design and analyze these new algorithms. When possible, code for the basic algorithms and their applications will be made available over the web to researchers.
The use of Spectral Graph Theory in computer science applications has become increasingly important and popular. A notable application is the algorithm patented by Google to rank order web pages. Other applications include image processing, in particular, medical image segmentation and denoising. This project will further contribute to the design of better algorithms for these problem domains by combining the best ideas from numerical analysis and graph theory. The goal is to design algorithms with very strong guarantees for both run time and robustness so that these algorithms will be appropriate for critical applications such as real-time image processing in a clinician's office. Dissemination will not only include journal and conference publications, but also giving a biannual spectral graph theory class and spectral graph theory lectures in both undergraduate and graduate algorithm classes.
