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 …

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 …

Estimation is the computational task of recovering a hidden parameter x associated with a
distribution D x, given a measurement y sampled from the distribution. High dimensional …

The Sum-of-Squares (SoS) hierarchy of semidefinite programs is a powerful algorithmic
paradigm which captures state-of-the-art algorithmic guarantees for a wide array of …

Abstract Principal Components Analysis (PCA) is a dimension-reduction technique widely
used in machine learning and statistics. However, due to the dependence of the principal …

A set of high dimensional points X ={x_1,x_2,...,x_n\}⊆R^d in isotropic position is said to be
δ-anti concentrated if for every direction v, the fraction of points in X satisfying …

We give efficient algorithms for finding power-sum decomposition of an input polynomial
P(x)=\displaystylei≦mp_i(x)^d with component p_is. The case of linear p_is is equivalent to …

Non-Gaussian Component Analysis (NGCA) is the statistical task of finding a non-Gaussian
direction in a high-dimensional dataset. Specifically, given iid samples from a distribution …

Analyzing concentration of large random matrices is a common task in a wide variety of
fields. Given independent random variables, several tools are available to bound the norms …

Given independent standard Gaussian points $ v_1,\ldots, v_n $ in dimension $ d $, for what
values of $(n, d) $ does there exist with high probability an origin-symmetric ellipsoid that …