  The smoothing parameter $\eta_{\epsilon}(\mathcal{L})$ of a Euclidean lattice
$\mathcal{L}$, introduced by Micciancio and Regev (FOCS'04; SICOMP'07), is
(informally) the smallest amount of Gaussian noise that "smooths out" the
discrete structure of $\mathcal{L}$ (up to error $\epsilon$). It plays a
central role in the best known worst-case/average-case reductions for lattice
problems, a wealth of lattice-based cryptographic constructions, and
(implicitly) the tightest known transference theorems for fundamental lattice
quantities.
  In this work we initiate a study of the complexity of approximating the
smoothing parameter to within a factor $\gamma$, denoted $\gamma$-${\rm
GapSPP}$. We show that (for $\epsilon = 1/{\rm poly}(n)$): $(2+o(1))$-${\rm
GapSPP} \in {\rm AM}$, via a Gaussian analogue of the classic
Goldreich-Goldwasser protocol (STOC'98); $(1+o(1))$-${\rm GapSPP} \in {\rm
coAM}$, via a careful application of the Goldwasser-Sipser (STOC'86) set size
lower bound protocol to thin spherical shells; $(2+o(1))$-${\rm GapSPP} \in
{\rm SZK} \subseteq {\rm AM} \cap {\rm coAM}$ (where ${\rm SZK}$ is the class
of problems having statistical zero-knowledge proofs), by constructing a
suitable instance-dependent commitment scheme (for a slightly worse
$o(1)$-term); $(1+o(1))$-${\rm GapSPP}$ can be solved in deterministic
$2^{O(n)} {\rm polylog}(1/\epsilon)$ time and $2^{O(n)}$ space.
  As an application, we demonstrate a tighter worst-case to average-case
reduction for basing cryptography on the worst-case hardness of the ${\rm
GapSPP}$ problem, with $\tilde{O}(\sqrt{n})$ smaller approximation factor than
the ${\rm GapSVP}$ problem.
  Central to our results are two novel, and nearly tight, characterizations of
the magnitude of discrete Gaussian sums.
