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/

Algorithms and Explicit Constructions via Spectral Techniques

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

Add event to Google
Add event to iCal