87 citations · 305 across the 39 of their papers we have counts for
6 papers · 1 filter
Private Robust Estimation by Stabilizing Convex Relaxations
Pravesh K. Kothari, Pasin Manurangsi, Ameya Velingker
We give the first polynomial time and sample -differentially private (DP) algorithm to estimate the mean, covariance and higher moments in the presence of a constant fracti…
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…
Algorithmic Thresholds for Refuting Random Polynomial Systems
Jun-Ting Hsieh, Pravesh K. Kothari
Consider a system of polynomial equations of degree in -dimensional variable such that each coefficient of every…
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…
Memory-Sample Lower Bounds for Learning Parity with Noise
Sumegha Garg, Pravesh K. Kothari, Pengda Liu +1
In this work, we show, for the well-studied problem of learning parity under noise, where a learner tries to learn from a stream of random linear…
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…