38 citations · 171 across the 26 of their papers we have counts for
40 papers
Noise stability on the Boolean hypercube via a renormalized Brownian motion
Ronen Eldan, Dan Mikulincer, Prasad Raghavendra
We consider a variant of the classical notion of noise on the Boolean hypercube which gives rise to a new approach to inequalities regarding noise stability. We use this approach t…
Matrix Discrepancy from Quantum Communication
Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty
We develop a novel connection between discrepancy minimization and (quantum) communication complexity. As an application, we resolve a substantial special case of the Matrix Spence…
On statistical inference when fixed points of belief propagation are unstable
Siqi Liu, Sidhanth Mohanty, Prasad Raghavendra
Many statistical inference problems correspond to recovering the values of a set of hidden variables from sparse observations on them. For instance, in a planted constraint satisfa…
List Decodable Subspace Recovery
Prasad Raghavendra, Morris Yau
Learning from data in the presence of outliers is a fundamental problem in statistics. In this work, we study robust statistics in the presence of overwhelming outliers for the fun…
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria +2
We study efficient algorithms for linear regression and covariance estimation in the absence of Gaussian assumptions on the underlying distributions of samples, making assumptions…
Extended Formulation Lower Bounds for Refuting Random CSPs
Jonah Brown-Cohen, Prasad Raghavendra
Random constraint satisfaction problems (CSPs) such as random -SAT are conjectured to be computationally intractable. The average case hardness of random -SAT and other CSPs…