Doctoral Thesis Proposal - Jeff Xu

— 4:00pm

Location:
In Person - Reddy Conference Room, Gates Hillman 4405

Speaker:
JEFF XU, Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://www.andrew.cmu.edu/user/sichaoxu/

In recent years, algorithmic challenges across diverse areas including statistical physics, machine learning and cryptography have centered around statistical inference problems, i.e., computational problems with average-case inputs. For many of these problems, the best-known efficient algorithms are often suboptimal, giving rise to information vs. computation gaps, discrepancies between what is theoretically possible given the amount of information and what can be attained via efficient algorithms. One fundamental question is how we can provide rigorous evidence of hardness to show that such gaps are insurmountable for efficient computation. 

We propose to provide rigorous evidence via the lens of the Sum-of-Squares (SoS) algorithms, a hierarchy of semidefinite programmings. Unlike several other popular models in the average-case setting (eg. low-degree polynomials/statistical-query/ overlap-gap). Sum-of-Squares algorithms are known to capture various optimal algorithms in both the average and worst-case setting, and therefore provide one of the strongest form of hardness. 

In this talk, I will illustrate that average-case SoS hardness usually boils down to the study of spectral techniques, specifically the study of random matrices with correlated input, and how a refined understanding of such matrices gives rise to the resolution of key average-case complexity questions including sparse graph independent-set, densest-k subgraph, and coloring. Finally, I will talk about some exciting challenges in the future along this direction, and specifically how they boil down again to simple-to-state, self-contained questions about random matrices, and explore the applications beyond average-case hardness.

Thesis Committee

Pravesh K. Kothari (Chair)
Aayush Jain
Ryan O’Donnell
Madhur Tulsiani (Toyota Technical Institute at Chicago / University of Chicago)

Additional Information

Add event to Google
Add event to iCal