research
∙
08/29/2023
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
A code C {0,1}^k →{0,1}^n is a q-locally decodable code (q-LDC) if one c...
share
research
∙
05/13/2022
Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number
Let ℋ(k,n,p) be the distribution on k-uniform hypergraphs where every su...
research
∙
05/13/2022
Sparsity and ℓ_p-Restricted Isometry
A matrix A is said to have the ℓ_p-Restricted Isometry Property (ℓ_p-RIP...
research
∙
10/22/2021
Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally
In this work, we revisit the problem of estimating the mean and covarian...
research
∙
09/09/2021
Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random"
We present an algorithm for strongly refuting smoothed instances of all ...
research
∙
08/31/2021
ℓ_p-Spread Properties of Sparse Matrices
Random subspaces X of ℝ^n of dimension proportional to n are, with high ...
research
∙
05/16/2021
A Stress-Free Sum-of-Squares Lower Bound for Coloring
We prove that with high probability over the choice of a random graph G ...
research
∙
05/30/2020