Approximate Spielman-Teng theorems

Combinatorics Seminar
Event time: 
Thursday, September 12, 2019 - 4:00pm
DL 431
Vishesh Jain
Speaker affiliation: 
Event description: 

An approximate Spielman-Teng theorem for the least singular value $s_n(M_n)$ of a random $n\times n$ matrix $M_n$ is a statement of the following form: there exist constants $C,c > 0$ such that for all $\eta \geq 0$, $\mathbb{P}(s_n(M_n) \leq \eta) \lesssim n^{C}\eta + \exp(-n^{c})$. I will discuss a novel combinatorial approach for proving such theorems in a fairly unified manner for a variety of random matrix models.

Research Area(s):