38 citations · 171 across the 26 of their papers we have counts for
16 papers · 1 filter
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…
Local Statistics, Semidefinite Programming, and Community Detection
Jess Banks, Sidhanth Mohanty, Prasad Raghavendra
We propose a new hierarchy of semidefinite programming relaxations for inference problems. As test cases, we consider the problem of community detection in block models. The vertic…
List Decodable Learning via Sum of Squares
Prasad Raghavendra, Morris Yau
In the list-decodable learning setup, an overwhelming majority (say a -fraction) of the input data consists of outliers and the goal of an algorithm is to output a small list…
High-dimensional estimation via sum-of-squares proofs
Prasad Raghavendra, Tselil Schramm, David Steurer
Estimation is the computational task of recovering a hidden parameter associated with a distribution , given a measurement sampled from the distribution. High dimensio…