Spectral methods have become ubiquitous in computer science. By analyzing the eigenvalues and eigenvectors of matrices naturally associated with a graph, such as its adjacency matrix, one can extract useful information about the graph's structure. Such methods have yielded the best-known results for a wide range of foundational problems.

In this thesis, we apply this "spectral lens" to prove new results in graph theory, design algorithms, and construct explicit vertex expanders. The results are divides into three parts:

• Part I. We develop spectral techniques to obtain new results in graph theory. These results are not only of independent interest but are also key ingredients in later parts of the thesis.
• Part II. We present algorithms for both refuting semirandom constraint satisfaction problems and recovering solutions in planted ones, both utilizing spectral information of the underlying hypergraph. Moreover, we give algorithms to find large independent sets in spectral expanders.
• Part III. We construct explicit constant-degree vertex expanders using the tripartite line product. First, we obtain explicit unique-neighbor expanders by instantiating the product using Ramanujan graphs – the optimal spectral expanders. Then, by replacing Ramanujan graphs with the incidence graphs of Ramanujan cubical complexes, we obtain the first explicit lossless vertex expanders.

209 pages

Thesis Committee:
Pravesh K. Kothari (Chair, CMU/Princeton)
Ryan O'Donnell
Jason Li
Venkatesan Gurusawmi (University of California, Berkeley)
David Steurer (ETH Zürich)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Creative Commons: CC-BY (Attribution)

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu