  In this paper, we introduce a variant of spectral sparsification, called
probabilistic $(\varepsilon,\delta)$-spectral sparsification. Roughly speaking,
it preserves the cut value of any cut $(S,S^{c})$ with an $1\pm\varepsilon$
multiplicative error and a $\delta\left|S\right|$ additive error. We show how
to produce a probabilistic $(\varepsilon,\delta)$-spectral sparsifier with
$O(n\log n/\varepsilon^{2})$ edges in time $\tilde{O}(n/\varepsilon^{2}\delta)$
time for unweighted undirected graph. This gives fastest known sub-linear time
algorithms for different cut problems on unweighted undirected graph such as
  - An $\tilde{O}(n/OPT+n^{3/2+t})$ time $O(\sqrt{\log n/t})$-approximation
algorithm for the sparsest cut problem and the balanced separator problem.
  - A $n^{1+o(1)}/\varepsilon^{4}$ time approximation minimum s-t cut algorithm
with an $\varepsilon n$ additive error.
