27 citations · 35 across the 10 of their papers we have counts for
4 papers · 1 filter
Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally
Pravesh K. Kothari, Peter Manohar, Brian Hu Zhang
In this work, we revisit the problem of estimating the mean and covariance of an unknown -dimensional Gaussian distribution in the presence of an -fraction of adver…
Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random"
Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
We present an algorithm for strongly refuting smoothed instances of all Boolean CSPs. The smoothed model is a hybrid between worst and average-case input models, where the input is…
-Spread and Restricted Isometry Properties of Sparse Random Matrices
Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff
Random subspaces of of dimension proportional to are, with high probability, well-spread with respect to the -norm. Namely, every nonzero i…
A Stress-Free Sum-of-Squares Lower Bound for Coloring
Pravesh K. Kothari, Peter Manohar
We prove that with high probability over the choice of a random graph from the Erdős-Rényi distribution , a natural -time, degree $O(\var…