  A $(\beta,\delta,\Delta)$-padded decomposition of an edge-weighted graph $G =
(V,E,w)$ is a stochastic decomposition into clusters of diameter at most
$\Delta$ such that for every vertex $v\in V$, the probability that
$\rm{ball}_G(v,\gamma\Delta)$ is entirely contained in the cluster containing
$v$ is at least $e^{-\beta\gamma}$ for every $\gamma \in [0,\delta]$. Padded
decompositions have been studied for decades and have found numerous
applications, including metric embedding, multicommodity flow-cut gap, muticut,
and zero extension problems, to name a few. In these applications, parameter
$\beta$, called the padding parameter, is the most important parameter since it
decides either the distortion or the approximation ratios. For general graphs
with $n$ vertices, $\beta = \Theta(\log n)$. Klein, Plotkin, and Rao showed
that $K_r$-minor-free graphs have padding parameter $\beta = O(r^3)$, which is
a significant improvement over general graphs when $r$ is a constant. A
long-standing conjecture is to construct a padded decomposition for
$K_r$-minor-free graphs with padding parameter $\beta = O(\log r)$. Despite
decades of research, the best-known result is $\beta = O(r)$, even for graphs
with treewidth at most $r$. In this work, we make significant progress toward
the aforementioned conjecture by showing that graphs with treewidth $\rm{tw}$
admit a padded decomposition with padding parameter $O(\log \rm{tw})$, which is
tight. As corollaries, we obtain an exponential improvement in dependency on
treewidth in a host of algorithmic applications: $O(\sqrt{ \log n \cdot
\log(\rm{tw})})$ flow-cut gap, max flow-min multicut ratio of
$O(\log(\rm{tw}))$, an $O(\log(\rm{tw}))$ approximation for the 0-extension
problem, an $\ell^{O(\log n)}_\infty$ embedding with distortion $O(\log
\rm{tw})$, and an $O(\log \rm{tw})$ bound for integrality gap for the uniform
sparsest cut.
