  Let $M_n$ denote a random symmetric $n \times n$ matrix whose upper diagonal
entries are independent and identically distributed Bernoulli random variables
(which take values $1$ and $-1$ with probability $1/2$ each). 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 singularity bound due to
Costello, Tao, and Vu (2005), and a bound of Nguyen (2011) showing that the
singularity probability decays faster than any polynomial. In this paper,
improving on all previous results, we show that the probability of singularity
of $M_n$ is at most $2^{-n^{1/4}\sqrt{\log{n}}/1000}$ for all sufficiently
large $n$. The proof utilizes and extends a novel combinatorial approach to
discrete random matrix theory, which has been recently introduced by the
authors together with Luh and Samotij.
