Spectral algorithms and spectral analysis form the basis for some of the most efficient and effective techniques in areas ranging from machine learning to scientific computing, from graphics to data mining, and from collaborative filtering to VLSI design. They also play a prominent role in combinatorial optimization, where they are used in algorithms for graph partitioning and constraint satisfaction. Despite the apparent utility of spectral techniques and the intense effort devoted to their analysis, our ability to reason about them rigorously is still very limited. This project addresses the development of an algorithmically-centered theory of spectral analysis which draws upon tools from contemporary mathematics, and is inspired by experimental evidence which has, so far, eluded a satisfactory theoretical explanation. The project also addresses the relative power of spectral methods from the viewpoint of computational complexity. This involves the both the study of what cannot be done using only information about eigenvalues and eigenvectors, as well as what can be achieved by combining spectral analysis with classical combinatorial approaches, like computation of graph flows.
