research
∙
08/12/2022
Noise stability on the Boolean hypercube via a renormalized Brownian motion
We consider a variant of the classical notion of noise on the Boolean hy...
share
research
∙
10/19/2021
Matrix Discrepancy from Quantum Communication
We develop a novel connection between discrepancy minimization and (quan...
research
∙
01/26/2021
Computational phase transitions in sparse planted problems?
In recent times the cavity method, a statistical physics-inspired heuris...
research
∙
02/07/2020
List Decodable Subspace Recovery
Learning from data in the presence of outliers is a fundamental problem ...
research
∙
12/23/2019
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
We study efficient algorithms for linear regression and covariance estim...
research
∙
11/07/2019
Extended Formulation Lower Bounds for Refuting Random CSPs
Random constraint satisfaction problems (CSPs) such as random 3-SAT are ...
research
∙
11/05/2019
Local Statistics, Semidefinite Programming, and Community Detection
We propose a new hierarchy of semidefinite programming relaxations for i...
research
∙
11/04/2019
Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4
The degree-4 Sum-of-Squares (SoS) SDP relaxation is a powerful algorithm...
research
∙
05/12/2019
List Decodable Learning via Sum of Squares
In the list-decodable learning setup, an overwhelming majority (say a 1-...
research
∙
07/30/2018
High-dimensional estimation via sum-of-squares proofs
Estimation is the computational task of recovering a hidden parameter x ...
research
∙
11/30/2017
Exponential lower bounds on spectrahedral representations of hyperbolicity cones
The Generalized Lax Conjecture asks whether every hyperbolicity cone is ...
research
∙
10/13/2017
The power of sum-of-squares for detecting hidden structures
We study planted problems---finding hidden structures in random noisy in...
research
∙
08/12/2017
Dimension Reduction for Polynomials over Gaussian Space and Applications
We introduce a new technique for reducing the dimension of the ambient s...
research
∙
12/03/2010