27 citations · 35 across the 10 of their papers we have counts for
12 papers
Strongly Refuting Semirandom Linear Systems in Subexponential Time
Pravesh K. Kothari, Andrew D. Lin, Peter Manohar
In this paper, we consider the problem of refuting -linear equations with random right-hand sides. Formally, we give a sub-exponential -time randomiz…
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…
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…
Sparsity and -Restricted Isometry
Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff
A matrix is said to have the -Restricted Isometry Property (-RIP) if for all vectors of up to some sparsity , is roughly proportional to $\|…
Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally
Pravesh K. Kothari, Peter Manohar, Brian Hu Zhang
In this work, we revisit the problem of estimating the mean and covariance of an unknown -dimensional Gaussian distribution in the presence of an -fraction of adver…
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…
-Spread and Restricted Isometry Properties of Sparse Random Matrices
Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff
Random subspaces of of dimension proportional to are, with high probability, well-spread with respect to the -norm. Namely, every nonzero i…
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…
Lower Bounds for Caching with Delayed Hits
Peter Manohar, Jalani Williams
Caches are a fundamental component of latency-sensitive computer systems. Recent work of [ASWB20] has initiated the study of delayed hits: a phenomenon in caches that occurs when t…