87 citations · 305 across the 39 of their papers we have counts for
51 papers
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold
Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari +1
We present an efficient algorithm to solve semirandom planted instances of any Boolean constraint satisfaction problem (CSP). The semirandom model is a hybrid between worst-case an…
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari +1
A code is a -locally decodable code (-LDC) if one can recover any chosen bit of the message with good confidence by…
Ellipsoid Fitting Up to a Constant
Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin +1
In [Sau11,SPW13], Saunderson, Parrilo and Willsky asked the following elegant geometric question: what is the largest such that there is an ellipsoid in th…
Is Planted Coloring Easier than Planted Clique?
Pravesh K. Kothari, Santosh S. Vempala, Alexander S. Wein +1
We study the computational complexity of two related problems: recovering a planted -coloring in , and finding efficiently verifiable witnesses of non--colorability…
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…