87 citations · 305 across the 39 of their papers we have counts for
18 papers · 1 filter
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…
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…
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…
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…