These notes survey and explore an emerging method, which we call the low-degree
method, for understanding statistical-versus-computational tradeoffs in high-dimensional …

We introduce a framework for proving lower bounds on computational problems over
distributions against algorithms that can be implemented using access to a statistical query …

We prove that with high probability over the choice of a random graph G from the Erdös--
Rényi distribution G(n,1/2), the n^O(d)-time degree d sum-of-squares (SOS) semidefinite …

We study planted problems-finding hidden structures in random noisy inputs-through the
lens of the sum-of-squares semidefinite programming hierarchy (SoS). This family of …

Inference problems with conjectured statistical-computational gaps are ubiquitous
throughout modern statistics, computer science, statistical physics and discrete probability …

Result diversification is an important aspect in web-based search, document summarization,
facility location, portfolio management, and other applications. Given a set of ranked results …

Researchers currently use a number of approaches to predict and substantiate information-
computation gaps in high-dimensional statistical estimation problems. A prominent …

Over the last twenty years, an exciting interplay has emerged between proof systems and
algorithms. Some natural families of algorithms can be viewed as a generic translation from …

We study the computational cost of recovering a unit-norm sparse principal component x∈
R n planted in a random matrix, in either the Wigner or Wishart spiked model (observing …

Given a graph and an integer k, Densest k-Subgraph is the algorithmic task of finding the
subgraph on k vertices with the maximum number of edges. This is a fundamental problem …