  Karger (STOC 1995) gave the first FPTAS for the network (un)reliability
problem, setting in motion research over the next three decades that obtained
increasingly faster running times, eventually leading to a
$\tilde{O}(n^2)$-time algorithm (Karger, STOC 2020). This represented a natural
culmination of this line of work because the algorithmic techniques used can
enumerate $\Theta(n^2)$ (near)-minimum cuts. In this paper, we go beyond this
quadratic barrier and obtain a faster FPTAS for the network unreliability
problem. Our algorithm runs in $m^{1+o(1)} + \tilde{O}(n^{1.5})$ time.
  Our main contribution is a new estimator for network unreliability in very
reliable graphs. These graphs are usually the bottleneck for network
unreliability since the disconnection event is elusive. Our estimator is
obtained by defining an appropriate importance sampling subroutine on a dual
spanning tree packing of the graph. To complement this estimator for very
reliable graphs, we use recursive contraction for moderately reliable graphs.
We show that an interleaving of sparsification and contraction can be used to
obtain a better parametrization of the recursive contraction algorithm that
yields a faster running time matching the one obtained for the very reliable
case.
