Event time:

Thursday, February 14, 2019 - 4:00pm

Location:

DL 431

Speaker:

Asaf Ferber

Speaker affiliation:

MIT

Event description:

Let $M_n$ be an $n\times n$ symmetric matrix with entries in $\pm 1$, chosen uniformly at random. It is widely conjectured that $M_n$ is singular with probability at most $(2+o(1))^{-n}$. On the other hand, the best known upper bound on the singularity probability of $M_n$, due to Vershynin (2011), is $2^{-n^c}$, for some unspecified small constant $c > 0$ (this improves on a polynomial bound due to Costello, Tao, and Vu (2005), and a bound of the form $n^{-\omega(1)}$due to Nguyen (2011) ).

In this talk, using a novel combinatorial approach, we show that the probability of singularity of $M_n$ is at most $2^{-n^{1/4}}$. We also discuss improvements for other models of discrete random matrices.

Joint work with Vishesh Jain

Research Area(s):