87 citations · 305 across the 39 of their papers we have counts for
14 papers · 1 filter
Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error
He Jia, Pravesh K . Kothari, Santosh S. Vempala
We present a polynomial-time algorithm for robustly learning an unknown affine transformation of the standard hypercube from samples, an important and well-studied setting for inde…
Algorithms approaching the threshold for semi-random planted clique
Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
We design new polynomial-time algorithms for recovering planted cliques in the semi-random graph model introduced by Feige and Kilian 2001. The previous best algorithms for this mo…
Polynomial-Time Power-Sum Decomposition of Polynomials
Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari +1
We give efficient algorithms for finding power-sum decomposition of an input polynomial with component s. The case of linear s is equivale…
List-Decodable Covariance Estimation
Misha Ivkov, Pravesh K. Kothari
We give the first polynomial time algorithm for \emph{list-decodable covariance estimation}. For any , our algorithm takes input a sample of size $…
Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm
Jun-Ting Hsieh, Pravesh K. Kothari
In this note, we describe a -factor approximation algorithm for Max-Cut on weighted graphs of degree . Here, is the worst-cas…
Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number
Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
Let be the distribution on -uniform hypergraphs where every subset of of size is included as an hyperedge with probability independently. In t…