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 thesis, we illustrate that many of these questions boil down to the study of random matrices that have entries being polynomials of the underlying input. More concretely, we 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.

468 pages

Thesis Committee:
Pravesh K. Koathari (Chair, Carnegie Mellon University / Princeton University)
Aayush Jain
Ryan O'Donnell
Madhur Tulsiani (Toyota Technological Institute at Chicago / University of Chicago)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu