
Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
We study the problem of efficiently refuting the kcolorability of a gra...
read it

Overlaps, Eigenvalue Gaps, and Pseudospectrum under real Ginibre and Absolutely Continuous Perturbations
Let G_n be an n × n matrix with real i.i.d. N(0,1/n) entries, let A be a...
read it

Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time
We exhibit a randomized algorithm which given a square n× n complex matr...
read it

Local Statistics, Semidefinite Programming, and Community Detection
We propose a new hierarchy of semidefinite programming relaxations for i...
read it

Vector Colorings of Random, Ramanujan, and LargeGirth Irregular Graphs
We prove that in sparse ErdősRényi graphs of average degree d, the vect...
read it

Gaussian Regularization of the Pseudospectrum and Davies' Conjecture
A matrix A∈C^n× n is diagonalizable if it has a basis of linearly indepe...
read it

Phase transitions and optimal algorithms in highdimensional Gaussian mixture clustering
We consider the problem of Gaussian mixture clustering in the highdimen...
read it
Jess Banks
is this you? claim profile