Doctoral Thesis Oral Defense - Jun-Ting Hsieh
— 2:30pm
Location:
In Person and Virtual - ET
-
McWilliam Classroom, Gates Hillman 4304 and Zoom
Speaker:
JUN-TING HSIEH
,
Ph.D. Candidate
Computer Science Department
Carnegie Mellon University
https://jthsieh.github.io/
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 talk, we apply this "spectral lens" to prove new results in graph theory, design algorithms, and construct explicit vertex expanders.
In the first part of this talk, we present algorithms for both refuting semi random 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.
In the second part of this talk, we introduce the tripartite line product to construct constant-degree vertex expanders. 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.
Thesis Committee
Pravesh K. Kothari (Chair, Carnegie Mellon University/Princeton University)
Ryan O'Donnell
Jason Li
Venkatesan Guruswami (University of California, Berkeley)
David Steurer (ETH Zürich)
In Person and Zoom Participation. See announcement.
For More Information:
matthewstewart@cmu.edu