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
∙
07/12/2023
Ellipsoid Fitting Up to a Constant
In [Sau11,SPW13], Saunderson, Parrilo and Willsky asked the following el...
research
∙
03/01/2023
Is Planted Coloring Easier than Planted Clique?
We study the computational complexity of two related problems: recoverin...
research
∙
02/23/2023
Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error
We present a polynomial-time algorithm for robustly learning an unknown ...
research
∙
12/15/2022
Privately Estimating a Gaussian: Efficient, Robust and Optimal
In this work, we give efficient algorithms for privately estimating a Ga...
research
∙
12/11/2022
Algorithms approaching the threshold for semi-random planted clique
We design new polynomial-time algorithms for recovering planted cliques ...
research
∙
11/23/2022
A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
A remarkable recent paper by Rubinfeld and Vasilyan (2022) initiated the...
research
∙
07/30/2022
Polynomial-Time Power-Sum Decomposition of Polynomials
We give efficient algorithms for finding power-sum decomposition of an i...
research
∙
07/22/2022
A simple and sharper proof of the hypergraph Moore bound
The hypergraph Moore bound is an elegant statement that characterizes th...
research
∙
06/22/2022
List-Decodable Covariance Estimation
We give the first polynomial time algorithm for list-decodable covarianc...
research
∙
06/18/2022
Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm
In this note, we describe a α_GW + Ω̃(1/d^2)-factor approximation algori...
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
∙
12/07/2021
Private Robust Estimation by Stabilizing Convex Relaxations
We give the first polynomial time and sample (ϵ, δ)-differentially priva...
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
∙
10/16/2021
Algorithmic Thresholds for Refuting Random Polynomial Systems
Consider a system of m polynomial equations {p_i(x) = b_i}_i ≤ m of degr...
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
∙
07/05/2021
Memory-Sample Lower Bounds for Learning Parity with Noise
In this work, we show, for the well-studied problem of learning parity u...
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
∙
12/03/2020
Robustly Learning Mixtures of k Arbitrary Gaussians
We give a polynomial-time algorithm for the problem of robustly estimati...
research
∙
11/12/2020
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates
We study efficient algorithms for Sparse PCA in standard statistical mod...
research
∙
09/17/2020
Strongly refuting all semi-random Boolean CSPs
We give an efficient algorithm to strongly refute semi-random instances ...
research
∙
02/17/2020
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG
In this work, we establish lower-bounds against memory bounded algorithm...
research
∙
02/13/2019
On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes
We study the expressive power of kernel methods and the algorithmic feas...
research
∙
06/25/2018
Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium
Several works have shown unconditional hardness (via integrality gaps) o...
research
∙
04/23/2018
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture
Dinur, Khot, Kindler, Minzer and Safra (2016) recently showed that the (...
research
∙
03/08/2018
Efficient Algorithms for Outlier-Robust Regression
We give the first polynomial-time algorithm for performing linear or pol...
research
∙
03/05/2018
An Analysis of the t-SNE Algorithm for Data Visualization
A first line of attack in exploratory data analysis is data visualizatio...
research
∙
01/30/2018
Surprise in Elections
Elections involving a very large voter population often lead to outcomes...
research
∙
11/30/2017
Outlier-robust moment-estimation via sum-of-squares
We develop efficient algorithms for estimating low-degree moments of unk...
research
∙
10/13/2017