  We study the lower tail behavior of the least singular value of an $n\times
n$ random matrix $M_n := M+N_n$, where $M$ is a fixed complex matrix with
operator norm at most $\exp(n^{c})$ and $N_n$ is a random matrix, each of whose
entries is an independent copy of a complex random variable with mean $0$ and
variance $1$. Motivated by applications, our focus is on obtaining bounds which
hold with extremely high probability, rather than on the least singular value
of a typical such matrix.
  This setting has previously been considered in a series of influential works
by Tao and Vu, most notably in connection with the strong circular law, and the
smoothed analysis of the condition number, and our results improve upon theirs
in two ways:
  (i) We are able to handle $\|M\| = O(\exp(n^{c}))$, whereas the results of
Tao and Vu are applicable only for $M = O(\text{poly(n)})$.
  (ii) Even for $M = O(\text{poly(n)})$, we are able to extract more refined
information -- for instance, our results show that for such $M$, the
probability that $M_n$ is singular is $O(\exp(-n^{c}))$, whereas even in the
case when $\xi$ is a Bernoulli random variable, the results of Tao and Vu only
give a bound of the form $O_{C}(n^{-C})$ for any constant $C>0$.
  As opposed to all previous works obtaining such bounds with error rate better
than $n^{-1}$, our proof makes no use either of the inverse Littlewood--Offord
theorems, or of any sophisticated net constructions. Instead, we show how to
reduce the problem from the (complex) sphere to (Gaussian) integer vectors,
where it is solved directly by utilizing and extending a combinatorial approach
to the singularity problem for random discrete matrices, recently developed by
Ferber, Luh, Samotij, and the author.
