Doctoral Thesis Proposal - Jun-Ting Hsieh

— 12:30pm

Location:
In Person - Blellock-Skees Conference Room, Gates Hillman 8115

Speaker:
JUN-TING HSIEH, Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://jthsieh.github.io/

Spectral Algorithms for Optimization beyond the Average-Case

Spectral algorithms involve using the eigenvalues and eigenvectors of matrices derived from the input for algorithm design and analysis. These techniques have achieved remarkable success across a wide range of computational problems. In particular, through the study of random matrices, spectral methods have been widely used to solve problems in average-case complexity, where the input is drawn from some random model. 

In this proposal, we explore the robustness of spectral algorithms for hybrids between worst-case and average-case input models. Many existing algorithms tend to “overfit” to the specific randomness of the input – they fail even with slight perturbations of the input models. First, we show that spectral algorithms succeed in both refuting semirandom constraint satisfaction problems (CSPs) and solving semirandom planted instances, generalizing results previously known only for fully random CSPs. Second, we demonstrate how upper bounds on the second eigenvalue of the adjacency matrix suffice for finding large independent sets in 3-colorable graphs, extending existing results for random 3-colorable graphs.

Finally, for future work, we aim to extend such ideas to worst-case instances by understanding the minimal assumptions necessary for algorithmic success. Moreover, we will explore the limitations of spectral algorithms and investigate formal connections between spectral algorithms and low-degree polynomials of the input. 

Thesis Committee 

Pravesh K. Kothari (Carnegie Mellon University/Princeton University)
Ryan O'Donnell
Jason Li
Venkatesan Guruswami (University of California, Berkeley)
David Steurer (ETH, Zürich)

Event Website:
https://csd.cmu.edu/calendar/doctoral-thesis-proposal-junting-hsieh