research
∙
07/24/2023
Optimality of Glauber dynamics for general-purpose Ising model sampling and free energy approximation
Recently, Eldan, Koehler, and Zeitouni (2020) showed that Glauber dynami...
share
research
∙
07/19/2023
Online Algorithms and Lower Bounds for Average-Case Matrix Discrepancy
We study the operator norm discrepancy of i.i.d. random matrices, initia...
research
∙
01/23/2023
Generic MANOVA limit theorems for products of projections
We study the convergence of the empirical spectral distribution of 𝐀𝐁𝐀 f...
research
∙
11/04/2022
A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
We prove that the degree 4 sum-of-squares (SOS) relaxation of the clique...
research
∙
03/11/2022
The spectrum of the Grigoriev-Laurent pseudomoments
Grigoriev (2001) and Laurent (2003) independently showed that the sum-of...
research
∙
11/04/2021
The discrepancy of unsatisfiable matrices and a lower bound for the Komlós conjecture constant
We construct simple, explicit matrices with columns having unit ℓ^2 norm...
research
∙
07/12/2021
Strong recovery of geometric planted matchings
We study the problem of efficiently recovering the matching between an u...
research
∙
12/03/2020
Average-Case Integrality Gap for Non-Negative Principal Component Analysis
Montanari and Richard (2015) asked whether a natural semidefinite progra...
research
∙
11/07/2020
Hypothesis testing with low-degree polynomials in the Morris class of exponential families
Analysis of low-degree polynomial algorithms is a powerful, newly-popula...
research
∙
09/15/2020
Positivity-preserving extensions of sum-of-squares pseudomoments over the hypercube
We introduce a new method for building higher-degree sum-of-squares lowe...
research
∙
08/27/2020
Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
We study the problem of efficiently refuting the k-colorability of a gra...
research
∙
06/05/2020
Linear Programming and Community Detection
The problem of community detection with two equal-sized communities is c...
research
∙
05/22/2020
The Average-Case Time Complexity of Certifying the Restricted Isometry Property
In compressed sensing, the restricted isometry property (RIP) on M × N s...
research
∙
07/26/2019
A Tight Degree 4 Sum-of-Squares Lower Bound for the Sherrington-Kirkpatrick Hamiltonian
We show that, if W∈R^N × N_sym is drawn from the gaussian orthogonal ens...
research
∙
07/26/2019
Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio
These notes survey and explore an emerging method, which we call the low...
research
∙
07/26/2019
Subexponential-Time Algorithms for Sparse PCA
We study the computational cost of recovering a unit-norm sparse princip...
research
∙
02/19/2019