research
∙
05/13/2022
Global Convergence of Hessenberg Shifted QR II: Numerical Stability
We develop a framework for proving rapid convergence of shifted QR algor...
share
research
∙
05/13/2022
Global Convergence of Hessenberg Shifted QR III: Approximate Ritz Values via Shifted Inverse Iteration
We give a self-contained randomized algorithm based on shifted inverse i...
research
∙
11/15/2021
Global Convergence of Hessenberg Shifted QR I: Dynamics
Rapid convergence of the shifted QR algorithm on symmetric matrices was ...
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
∙
05/18/2020
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...
research
∙
12/18/2019
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...
research
∙
11/05/2019
Local Statistics, Semidefinite Programming, and Community Detection
We propose a new hierarchy of semidefinite programming relaxations for i...
research
∙
07/04/2019
Vector Colorings of Random, Ramanujan, and Large-Girth Irregular Graphs
We prove that in sparse Erdős-Rényi graphs of average degree d, the vect...
research
∙
06/27/2019
Gaussian Regularization of the Pseudospectrum and Davies' Conjecture
A matrix A∈C^n× n is diagonalizable if it has a basis of linearly indepe...
research
∙
10/10/2016