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