87 citations · 305 across the 39 of their papers we have counts for
8 papers · 1 filter
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…
A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
Aravind Gollakota, Adam R. Klivans, Pravesh K. Kothari
A remarkable recent paper by Rubinfeld and Vasilyan (2022) initiated the study of \emph{testable learning}, where the goal is to replace hard-to-verify distributional assumptions (…
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…
A simple and sharper proof of the hypergraph Moore bound
Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty
The hypergraph Moore bound is an elegant statement that characterizes the extremal trade-off between the girth - the number of hyperedges in the smallest cycle or even cover (a sub…
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…