Doctoral Thesis Proposal - Jun-Ting Hsieh October 3, 2024 11:00am — 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'DonnellJason LiVenkatesan Guruswami (University of California, Berkeley)David Steurer (ETH, Zürich) Event Website: https://csd.cmu.edu/calendar/doctoral-thesis-proposal-junting-hsieh Add event to Google Add event to iCal