Doctoral Thesis Oral Defense - Jeff Xu

— 3:30pm

Location:
In Person and Virtual - ET - Reddy Conference Room, Gates Hillman 4405 and Zoom

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

Spectral Techniques for Average-Case Complexity and Beyond

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. 

In this talk, I will demonstrate that many of these questions boil down to the study of random matrices that have entries being polynomials of the underlying input. More concretely, I will highlight the recent advances in the past few years that lead to a significantly more refined understanding of these ostensibly complicated matrices, and some intriguing questions around them that still remain after years of attacks.  The sharper understanding of these matrices ultimately allows us 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 average-case complexity.

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

In Person and Zoom Participation.  See announcement. 

For More Information:
matthewstewart@cmu.edu

Add event to Google
Add event to iCal