Jun-Ting Hsieh

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.