5 citations · 6 across the 6 of their papers we have counts for
5 papers · 1 filter
Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
Pravesh K. Kothari, Peter Manohar
We give improved lower bounds for binary -query locally correctable codes (3-LCCs) . Specifically, we prove: (1) If is a linear des…
An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes
Pravesh K. Kothari, Peter Manohar
We prove that the blocklength of a linear -query locally correctable code (LCC) with distance must be at least $n \g…
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…
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…